我正在构建一个递归的数独求解器，但是遇到了一个问题。看来我的合法性功能在最终答案中接受0。它没有分配零，但是零被用作占位符以标记未填充的值。当我运行程序时，我得到这样的输出...
**************************************************
7 4 3 | 8 2 1 | 0 0 0
0 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 0 0
0 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 0
0 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 0
2 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
正如您在解开谜题的这些打印输出中所看到的那样，它接受零作为第一列中的最后一个数字。我无法在代码中找到任何允许发生这种情况的地方。另外，我在编译时注意到有时我会以为我应该进入的内存会碰到，但它让我得以前进。我觉得有时候我的功能有些虚脱。
这是我的合法功能：
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] != 0){
if(present[(theBoard[row][i]) - 1]){
return false;
}
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
bool Board::isColumnLegal(int column){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[i][column] != 0){
if(present[(theBoard[i][column]) - 1]){
return false;
}
present[(theBoard[i][column]) - 1] = true;
}
}
return true;
}
bool Board::isPanelLegal(int rowStart, int colStart){
// Store the numbers in the panel in one vector.
vector<int> currentPanel;
for(int i = rowStart; i < rowStart + THREE; ++i){
cout << endl;
for(int j = colStart; j < colStart + THREE; ++j){
cout << theBoard[i][j];
currentPanel.push_back(theBoard[i][j]);
}
}
bool present[9] = {};
cout << endl << currentPanel.size() << endl;
for(int k = 0; k < currentPanel.size(); ++k){
if(currentPanel[k] != 0){
if(present[currentPanel[k] - 1]){
return false;
}
present[currentPanel[k] - 1] = true;
}
}
return true;
}
我知道它会与下标混淆，但是作为一般规则，为了找到数字，我从下标一开始。因此，第一行第一列中的7是坐标1、1。不是0、0。
我认为这是一个必然的问题，也许我不是一次检查所有数字，但是我年轻的编程人员却没有看到它。
也有人可以解释为什么我必须在isPanelLegal中放入present [currentPanel [k]-1]。我可以看到为什么在其他地方，因为向量从1开始，但是在isPanelLegal中，向量是从0开始，因为我刚刚在函数的第一部分中创建了它。它与-1一起使用，没有-1就无法使用。
递归部分...
if(board.isBoardFull()){
cout << "here" << endl;
board.display(outStream);
return true;
}
for(int i = ONE; i <= NINE; ++i){
for(int j = ONE; j <= NINE; ++j){
//cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
if(board.getSquare(i, j) == ZERO){
//cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
for(int k = ONE; k <= NINE; ++k){
board.setSquare(i, j, k);
if(board.isLegal(1, 10, 1, 10)){
board.display(outStream);
addSquare(depth, outStream);
return true;
}
board.unsetSquare(i, j);
}
}
}
}
board.display(outStream);
return false;
}
谢谢。
最佳答案
我认为您的问题在这里：
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] != 0){ // This line
if(present[(theBoard[row][i]) - 1]){
return false;
}
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
在for循环中，如果每个数字均为0，则该函数将返回true。如果发现0，您需要做的是返回false（假设0永远是不合法的，我认为数独就是这种情况）。
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] == 0)
return false;
if(present[(theBoard[row][i]) - 1])
return false;
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
列相同。
编辑：哦，我刚刚意识到您可能还需要在for循环中执行i
关于c++ - Sudoku递归，接受零为合法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19649673/