c++ - 数独递归，接受零为合法

Question

我正在构建一个递归数独求解器，但我遇到了一个问题。看来我的合法性功能在最终答案中接受 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;
}

我知道它与下标混淆，但作为一般规则，我从下标 1 开始，以便找到数字。所以第一行第一列的7是坐标1, 1，不是0, 0。

我相信这是一个有约束力的问题，也许我没有在一个实例中检查所有数字，但是我年轻的编程眼睛没有看到它。

也有人可以解释为什么我必须在 isPanelLegal 中放置 present[currentPanel[k] - 1]。我明白为什么在其他人中，因为 vector 从 1 开始，但在 isPanelLegal 中， vector 从零开始，因为我刚刚在函数的第一部分创建了它。它与 -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;
}

谢谢。

Answer 1

我认为您的问题出在这里:

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 <= theBoard.size() 。如果您尝试从 1 到 9 并且棋盘大小为 9，则 < 将带您从 1 到 8。正如其他人所说，这是您应该从 0 开始的另一个原因。如果您在没有正当理由的情况下从 1 开始一个数组，事情就会变得困惑。