1

我正在构建一个递归数独求解器，但我遇到了一个问题。看来我的合法性功能在最终答案中接受 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 中，向量从零开始，因为我刚刚在函数的第一部分创建了它。它与 -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;
}

谢谢你。

4

1 回答 1

0

我认为你的问题在这里：

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 开始数组，事情就会变得混乱。

于 2013-10-29T05:07:10.383 回答