高效非图求解器

Question

所以我最近看到了英国GCHQ发布的这个拼图：

它涉及到求解一个25x25的非图：

非图形是一种图像逻辑谜题，网格中的单元格必须根据网格一侧的数字来显示隐藏的图像，或者保留空白。在这种拼图类型中，数字是一种离散层析成像的形式，它测量在任何给定的行或列中填充的正方形中有多少条不间断的直线。例如，一条“4-8-3”的线索意味着有四个、八个和三个填充方块的集合，按顺序排列，在连续组之间至少有一个空白方块。

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

我在几个5x5的谜题上测试了它，它工作得很好。问题是，计算25x25GCHQ难题花费的时间太长了。我需要方法，使这个算法更有效-足够，以便它可以解决上面的谜题。有什么想法吗？

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

// 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的概念(理解示例)
• 按位运算：我很依赖它们，所以如果你对它不太熟悉的话，就读它吧。
• 图遍历算法：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，并将它们添加到可能的排列列表中。

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, ...
}

实现每行的验证

• 验证行的：

琐碎:我们将使用预先计算的排列，这样我们就不需要对每一行进行任何额外的验证。

• 验证列的：

在这里，我为每一行和每列保留当前块大小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
        }
    }
}

现在，我们可以使用这些索引/值来确定下一行中哪些位被期望为false/true。

用于验证的数据结构：

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

当设置上一行中的位时，当当前大小仍然小于当前索引的预期大小时，我们期望当前行中的位设置为true。否则，它必须是0，因为您希望在当前行中切断它。

或者，当最后一个块大小已经用于列时，我们就不能启动一个新块。因此，位必须是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;
}