c++ - 数独解算器程序

从solveSudoku函数调用main()函数。

我写了以下函数来解决数独问题:

#include <iostream>
#include <vector>
using namespace std;

int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
    for(int t = 0; t < 9; t++) {
        if(A[t][j] == k) //Checking jth column
            return 0;
        if(A[i][t] == k) //Checking ith row
            return 0;
        if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
            return 0;
    }
    return 1;
}

bool sudoku(vector<vector<char> > &A, int i, int j) {

    if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
        return true;

    if(A[i][j] == '.') {
        for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
            if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
                A[i][j] = k;
                if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block
                    return true;
                else
                    A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
            }
        }
    }

    else {
        if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))
            return true;
    }
    return false;//This should trigger backtracking
}

void solveSudoku(vector<vector<char> > &A) {
    sudoku(A, 0, 0);
}

int main() {
    vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
                               {'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
                               {'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
    solveSudoku(A);
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cout<<A[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

输出

5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
3 1 4 5 8 2 6 7 9

预期输出

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

当在solveSudoku函数中调用main()时，将输入数独作为参数提供。它由代表空字符的从1到9和.的字符组成。 solveSudoku函数的工作是正确填充数独中的所有元素(在适当的位置更改A中的值)。但是我得到了错误的答案。假定输入的数独输入是可解的。

正如Fezvez所说，我还认为算法中的问题在于if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))语句。我认为在用有效字符填充单元格后，该语句应递归检查右侧，向下和对角线的块是否也被填充。如果是，则数独解决了，它应该返回true，但是如果三个数中的任何一个失败，则应该回溯。但是为什么不这样做呢？

最佳答案

重做答案:sudoku(A, i, j)具有在A中写入数据的副作用。
当您调用if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))时，您击中了第二个检查sudoku(A, i, j+1)，它不再是相同的A，并且您没有测试您的想法。我通过更改if出现的两行并仅进行一次检查来解决此问题:sudoku(A, (i+1)%9, j+(i+1)/9)
旧答案:您的代码失败，因为sudoku的行为不像您想象的那样。您应该使用深度优先搜索探索进行回溯。但是您没有这样做:if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))既不是BFS也不是DFS，它会使您的算法失败

这是一个稍作修改的版本，其中我用sudoku(A, (i+1)%9, j+(i+1)/9)替换了有问题的部分，并且可以正常工作。

编辑:if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))是犯罪者，其原因如下:

sudoku(A, i, j)如果从(i，j)到右下角的任何矩形包含有效填充，则为true。即您可以输入数字，并且它们不违反数独规则。确实，您要计算的是sudoku(A,0,0)

但我将举一个失败的例子:假设您正在计算if(sudoku(A,1,0) && sudoku(A,0,1) && sudoku(A,1,1))。您以sudoku(A, 1, 0)开头并返回true。现在，您几乎可以填充所有A(顶行除外)。您可以继续计算sudoku(A,0,1)，但是如果您之前进行的几乎完全填充实际上是无效的(无法填充第一行)，则您的算法会立即失败

换句话说，您的代码失败，因为调用sudoku(A, i, j)具有副作用(用A写入数据)，并且当您在if中命中第三个 bool 值的第二个时，您没有处理正确的A

这是用您的示例更新的代码

#include <iostream>
#include <vector>
using namespace std;

int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
    for(int t = 0; t < 9; t++) {
        if(A[t][j] == k) //Checking jth column
            return 0;
        if(A[i][t] == k) //Checking ith row
            return 0;
        if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
            return 0;
    }
    return 1;
}

bool sudoku(vector<vector<char> > &A, int i, int j) {

    if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
        return true;

    if(A[i][j] == '.') {
        for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
            if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
                A[i][j] = k;
                if(sudoku(A, (i+1)%9, j+(i+1)/9))// CHANGE ONE
                    return true;
                else
                    A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
            }
        }
    }

    else {
        if(sudoku(A, (i+1)%9, j+(i+1)/9)) // CHANGE TWO
            return true;
    }
    return false;//This should trigger backtracking
}

void solveSudoku(vector<vector<char> > &A) {
    sudoku(A, 0, 0);
}

int main() {
    vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
                               {'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
                               {'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
    solveSudoku(A);
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cout<<A[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

输出

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9