-1

我写了一个数独求解器，当数独可解时它工作得很好。但是，当数独无法解决时，它会在回溯时更改谜题的原始数字。

bool Sudoku::solve(int row, int col){
if (board[row][col] != 0){
    int next_col = col;
    int next_row = row;

    next_col++;

    if (next_col > 8){
        next_row++;
        next_col = 0;
    }

    if (next_row > 8){
        return true;
    } else {
        if (solve(next_row, next_col))
            return true;
    }
}

for (int number = 1; number <= 9; number++){
    board[row][col] = number;

    if (check_row(row, number)
     && check_col(col, number)
     && check_box(row, col, number)){
        int next_row = row;
        int next_col = col+1;

        if (next_col > 8){
            next_col = 0;
            next_row++;
        }

        if (next_row > 8){
            return true;
        }

        if (solve(next_row, next_col))
            return true;
     }
}

board[row][col] = 0;
return false;

}

board 是一个 2D int 数组。我知道我可以使用某种结构而不是整数，它会存储数字是否最初存在，但是这个解决方案对我来说并不是很有吸引力。还有其他方法吗？

4

2 回答 2

2

在开始的检查中，当单元格被设置时，

if (board[row][col] != 0){
    int next_col = col;
    int next_row = row;

    next_col++;

    if (next_col > 8){
        next_row++;
        next_col = 0;
    }

    if (next_row > 8){
        return true;
    } else {
        if (solve(next_row, next_col))
            return true;
    }
}

添加一个

else {
    return false;
}

或将最后一个更改为

return solve(next_row, next_col);

以避免更改给定的数字。照原样，如果无法解决难题 - 即使在错误地猜测了可以解决原始单元格的前一个单元格之后 - 它会很高兴地继续更改单元格中的数字。

于 2013-03-21T00:06:21.830 回答
0

您可以创建一组所有访问过的位置。

一个示例实现是创建std::set<pair<int, int> > visited包含已访问的每个位置。然后，如果该位置已被访问，则不要更改该值。

于 2013-03-21T00:03:29.283 回答