c - 回溯所有答案

Question

我这里有这段代码。当您解决数独问题时，它工作得很好。

int solveBoard(int board[SIZE][SIZE], int rowPos, int colPos) {
    int newValueToCheck, oldRowPos, oldColPos;
    if (rowPos == SIZE) return 1;
    if (board[rowPos][colPos] != 0) {
        if (colPos == SIZE - 1) {
            rowPos++;
            colPos = 0;
        } else colPos++;
        if (solveBoard(board, rowPos, colPos) == 1) return 1;
        return 0;
    } for (newValueToCheck = 1; newValueToCheck <= SIZE; newValueToCheck++)
        if (checkBoard(board, newValueToCheck, rowPos, colPos) == 1) {
            board[rowPos][colPos] = newValueToCheck;
            oldRowPos = rowPos; 
            oldColPos = colPos;
            if (colPos == SIZE - 1) {
                rowPos++;
                colPos = 0;
            } else colPos++;
            if (solveBoard(board, rowPos, colPos) == 1) return 1;
            rowPos = oldRowPos;
            colPos = oldColPos;
            board[rowPos][colPos] = 0;
        }
    return 0;
}

唯一的问题是，我想获得所有可能的答案。我将如何修改它并获得所有可能的答案。

Answer 1

找到解决方案后不要回溯搜索。因此，在您尝试新值并忽略其返回值的地方进行简单的递归调用:

solveBoard(board, rowPos, colPos);

然后是递归末尾的每个解决方案:

if (rowPos == SIZE) printSolution(); return 1;