高效的 Nonogram 求解器
Efficient Nonogram Solver
所以我最近看到这个 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
}
}
}
我已经在 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
预先计算每行的所有排列。
排列也以按位表示形式存储。如果第一位填充第一列等，则第一位设置为真。
这既节省时间又 space 高效。对于计算，我们首先计算可以添加的额外 space 的数量。
这是number_of_columns - sum_of_blocksize - (number_of_blocks-1)
Dfs 遍历放置额外 spaces 的所有可能排列。查看 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
}
}
}
现在我们可以使用这些 index/values 来确定下一行中哪些位应该是 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
当设置上一行中的位时，当且仅当当前大小仍然小于当前索引的预期大小时，我们期望当前行中的位设置为真。否则它必须为 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 部分和您自己的一样简单。
如果行掩码符合当前配置，我们可以更新列 indices/values 并遍历到下一行并最终在 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;
}
所以我最近看到这个 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
}
}
}
我已经在 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
预先计算每行的所有排列。
排列也以按位表示形式存储。如果第一位填充第一列等，则第一位设置为真。 这既节省时间又 space 高效。对于计算，我们首先计算可以添加的额外 space 的数量。
这是number_of_columns - sum_of_blocksize - (number_of_blocks-1)
Dfs 遍历放置额外 spaces 的所有可能排列。查看 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
}
}
}
现在我们可以使用这些 index/values 来确定下一行中哪些位应该是 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
当设置上一行中的位时，当且仅当当前大小仍然小于当前索引的预期大小时，我们期望当前行中的位设置为真。否则它必须为 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 部分和您自己的一样简单。 如果行掩码符合当前配置，我们可以更新列 indices/values 并遍历到下一行并最终在 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;
}