所以最近看到英国GCHQ发的这个谜题：
它涉及求解 25x25 非图：
非图是图片逻辑谜题，其中网格中的单元格必须根据网格一侧的数字着色或留空，以显示隐藏的图片。在这种拼图类型中，数字是离散断层扫描的一种形式，用于测量任何给定的行或列中有多少完整的实心正方形线。例如，“4 8 3”的线索意味着有四个、八个和三个实心方块按顺序排列，连续组之间至少有一个空白方块。
自然地，我倾向于尝试编写一个可以为我解决问题的程序。我正在考虑从第 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
}
}
}