algorithm - 高效的 Nonogram 求解器

Question

所以我最近看到了这个puzzle英国 GCHQ 发布:

它涉及解决一个 25x25 的非图:

A nonogram is picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups."

自然而然地，我倾向于尝试编写一个可以为我解决问题的程序。我正在考虑一个从第 0 行开始的递归回溯算法，并且对于给定行线索中的信息的该行的每种可能排列，它放置下一行的可能组合并验证它是否是给定列的有效放置线索。如果是，则继续，如果不是，则回溯，直到所有行都放置在有效配置中，或者所有可能的行组合都已用尽。

我在几个 5x5 拼图上对其进行了测试，效果非常好。问题是计算 25x25 GCHQ 难题花费的时间太长。我需要使该算法更高效的方法 - 足以解决上面链接的难题。有什么想法吗？

这是我为每一行生成一组行可能性的代码以及求解器的代码(注意*它使用了一些非标准库，但这不应该影响重点):

// The Vector<int> input is a list of the row clues eg. for row 1, input = {7,3,1,1,7}. The 
// int currentElemIndex keeps track of what block of the input clue we are dealing with i.e 
// it starts at input[0] which is the 7 sized block and for all possible places it can be 
// placed, places the next block from the clue recursively.

// The Vector<bool> rowState is the state of the row at the current time. True indicates a 
// colored in square, false indicates empty.

// The Set< Vector<bool> >& result is just the set that stores all the possible valid row 
// configurations. 

// The int startIndex and endIndex are the bounds on the start point and end point between 
// which the function will try to place the current block. The endIndex is calculated by 
// subtracting the width of the board from the sum of the remaining block sizes + number 
// of blocks remaining. Ie. if for row 1 with the input {7,3,1,1,7} we were placing the 
// first block, the endIndex would be (3+1+1+7)+4=16 because if the first block was placed
// further than this, it would be impossible for the other blocks to fit. 

// BOARD_WIDTH = 25;

// The containsPresets funtion makes sure that the row configuration is only added to the 
// result set if it contains the preset values of the puzzle (the given squares
// at the start of the puzzle).



void Nonogram::rowPossibilitiesHelper(int currentElemIndex, Vector<bool>& rowState, 
                                         Vector<int>& input, Set< Vector<bool> >& result, 
                                            int startIndex, int rowIndex) {
    if(currentElemIndex == input.size()) {         
        if(containsPresets(rowState, rowIndex)) {
            result += rowState;
        }
    } else {
        int endIndex = BOARD_WIDTH - rowSum(currentElemIndex+1, input);
        int blockSize = input[currentElemIndex];
        for(int i=startIndex; i<=endIndex-blockSize; i++) {
            for(int j=0; j<blockSize; j++) {
                rowState[i+j] = true;                                                                       // set block
            }
            rowPossibilitiesHelper(currentElemIndex+1, rowState, input, result, i+blockSize+1, rowIndex);   // explore
            for(int j=0; j<blockSize; j++) {
                rowState[i+j] = false;                                                                      // unchoose
            }
        }
    }
}


// The function is initally passed in 0 for the rowIndex. It gets a set of all possible 
// valid arrangements of the board and for each one of them, sets the board row at rowIndex
// to the current rowConfig. Is then checks if the current configuration so far is valid in 
// regards to the column clues. If it is, it solves the next row, if not, it unmarks the 
// current configuration from the board row at rowIndex.

void Nonogram::solveHelper(int rowIndex) {
    if(rowIndex == BOARD_HEIGHT) {
        printBoard();
    } else {
        for(Vector<bool> rowConfig : rowPossisbilities(rowIndex)) {
            setBoardRow(rowConfig, rowIndex);
            if(isValidConfig(rowIndex)) {                           // set row
                solveHelper(rowIndex+1);                            // explore
            }
            unsetBoardRow(rowIndex);                                // unset row
        }
    }
}

Answer 1

我已经用 Java 做了一个解决方案，对于您的示例拼图 (25x25)，它可以在大约 50ms 内解决。

完整代码和输入示例:Github

---

先决条件

• Java 的概念(理解示例)
• Bitwise operations : 我非常依赖它们，所以如果您不是很熟悉，请阅读它。
• 图遍历算法:DFS

给定:

R, C // number of rows, columns
int[][] rows; // for each row the block size from left to right (ex: rows[2][0] = first blocksize of 3 row)
int[][] cols; // for each column the block size from top to bottom
long[] grid; // bitwise representation of the board with the initially given painted blocks

预先计算每行的所有排列。

排列也存储在按位表示中。如果第一位填充第一列等，则第一位设置为真。 这既节省时间又节省空间。对于计算，我们首先计算可以添加的额外空间的数量。

这是number_of_columns - sum_of_blocksize - (number_of_blocks-1)

Dfs 遍历放置额外空格的所有可能排列。请参阅 calcPerms 并将它们添加到可能的排列列表中(如果它与最初给定的绘制 block 匹配)。

rowPerms = new long[R][];
for(int r=0;r<R;r++){
    LinkedList<Long> res = new LinkedList<Long>();
    int spaces = C - (rows[r].length-1);
    for(int i=0;i<rows[r].length;i++){
        spaces -= rows[r][i];
    }
    calcPerms(r, 0, spaces, 0, 0,res);
    rowPerms[r] = new long[res.size()];
    while(!res.isEmpty()){
        rowPerms[r][res.size()-1]=res.pollLast();
    }
}
...

// row, current block in row, extra spaces left to add, current permutation, current number of bits to shift
static void calcPerms(int r, int cur, int spaces, long perm, int shift, LinkedList<Long> res){
    if(cur == rows[r].length){
        if((grid[r]&perm)==grid[r]){
            res.add(perm);                
        }
        return;
    }
    while(spaces>=0){
        calcPerms(r, cur+1, spaces, perm|(bits(rows[r][cur])<<shift), shift+rows[r][cur]+1,res);
        shift++;
        spaces--;
    }
}
static long bits(int b){
    return (1L<<b)-1; // 1 => 1, 2 => 11, 3 => 111, ...
}

每行执行验证

• 验证行:

[琐碎:] 我们将使用预先计算的排列，因此我们不需要对每行进行任何额外的验证。

• 验证列:

为此，我为每一行和每一列保留当前 block 大小 colIx 的索引，以及该大小 colVal 中的位置。

这是根据上一行的值和索引计算的:

• 如果列在当前行中绘制，则值增加 1。
• 如果该列在前一行中绘制但不在当前行中，则值重置为 0，索引增加 1。

示例:

static void updateCols(int row){
    long ixc = 1L;
    for(int c=0;c<C;c++,ixc<<=1){
        // copy from previous
        colVal[row][c]=row==0 ? 0 : colVal[row-1][c];
        colIx[row][c]=row==0 ? 0 : colIx[row-1][c];
        if((grid[row]&ixc)==0){
            if(row > 0 && colVal[row-1][c] > 0){ 
                // bit not set and col is not empty at previous row => close blocksize
                colVal[row][c]=0;
                colIx[row][c]++;
            }
        }else{
            colVal[row][c]++; // increase value for set bit
        }
    }
}

现在我们可以使用这些索引/值来确定下一行中哪些位预计为假/真。

用于验证的数据结构:

static long[] mask; // per row bitmask, bit is set to true if the bit has to be validated by the val bitmask
static long[] val; // per row bitmask with bit set to false/true for as expected for the current row

当设置前一行中的位时，当且仅当当前大小仍然小于当前索引的预期大小时，我们期望当前行中的位设置为真。否则它必须为 0，因为您想在当前行将其切断。

或者当最后一个 block 大小已经用于该列时，我们无法开始一个新 block 。因此位必须为 0。

static void rowMask(int row){
    mask[row]=val[row]=0;
    if(row==0){
        return;
    }
    long ixc=1L;
    for(int c=0;c<C;c++,ixc<<=1){
        if(colVal[row-1][c] > 0){
            // when column at previous row is set, we know for sure what has to be the next bit according to the current size and the expected size
            mask[row] |= ixc; 
            if(cols[c][colIx[row-1][c]] > colVal[row-1][c]){
                val[row] |= ixc; // must set
            }
        }else if(colVal[row-1][c] == 0 && colIx[row-1][c]==cols[c].length){
            // can not add anymore since out of indices
            mask[row] |= ixc;
        }
    }
}

Dfs 所有行并检查是否仍然有效

这使得实际的 dfs 部分和您自己的一样简单。 如果行掩码适合当前配置，我们可以更新列索引/值并遍历到下一行并最终在 R 行结束。

static boolean dfs(int row){
    if(row==R){
        return true;
    }
    rowMask(row); // calculate mask to stay valid in the next row
    for(int i=0;i<rowPerms[row].length;i++){
        if((rowPerms[row][i]&mask[row])!=val[row]){
            continue;
        }
        grid[row] = rowPerms[row][i];
        updateCols(row);
        if(dfs(row+1)){
            return true;
        }
    }
    return false;
}