数独求解程序

Question

数独求解程序

6

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

在调用 `main()` 函数中的 `solveSudoku` 函数时，将输入的数独作为参数传递。它由字符 `1` 到 `9` 和代表空字符的点号 `.` 组成。`solveSudoku` 函数的工作是正确填写数独中的所有元素（在原地更改 `A` 中的值）。但我得到了错误的答案。给定的输入数独可解决。正如 Fezvez 所说，我认为我的算法问题在于这个语句 `if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))`。我认为，在使用有效字符填充单元格后，此语句应该递归地检查右侧、下方和对角线上的块是否也被填充。如果是，则数独已解决，应返回 true，但如果其中任何一个失败，它应该回溯。但是为什么它没有这样做呢？

- Gyanshu

1

请发布一个 [mcve]。 - R Sahu

请问您能否大致告诉我您的算法应该如何工作，因为所有这些变量 i、j 和 d 让我有点困惑。 - Florian p.i.

@Florianp.i. 我在代码中添加了更多的注释。i，j是当前考虑的数独的坐标，我的代码中没有变量d。 - Gyanshu

相当简单和直接的求解器 - sp2danny

3个回答

3

我改写了您的代码，并替换了一些内容，以便更容易进行调试。它看起来不像是一个典型的递归函数，因为只有一个参数作为引用传递，但实际上是递归函数，因为它使用堆栈来处理 y、x 和 k。（已经修正）

这是修改后的函数：

bool sudoku(vector<vector<char> > &A)
{
    //Test full sudoku field to see if all fields can be filled with valid numbers:
    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
        {
            if (A[x][y] == '.') //Startpoint to find a valid replacement:
            {
                for (char k = '1'; k <= '9'; k++)//At least one character has to be possible
                {
                    if (isvalid(k, A, x, y)) //If putting character `k` doesn't makes the sudoku invaild put it in:
                    {
                        A[x][y] = k;

                        //Try solving sudoku with new value:
                        if (sudoku(A))
                            return true;
                    }
                }
                //Reset to unsolved:
                A[x][y] = '.';
                return false;
            }
        }
    }
    //Reachable, if all fields are filled. [Corrected]
    //Assumption: Initialized with a valid field.
    //So a valid start field + valid adds ->always valid filled field
    //Otherwise you will have to test the complete field here.
    return true;
}

输出结果如下：

我非常确定你的问题在于这段代码：

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;

如果您查看输出和期望的输出，您会发现底部是唯一完全填充的行。这表明存在错误的反馈条件，但很难调试。这就是为什么我选择重写很多代码并删除不必要的代码的原因。

- Florian p.i.

你的程序很不错，但是你没有回答我的问题。还是给你一个赞，因为你修改了我的代码并提供了正确的程序。 - Gyanshu

谢谢，对我来说主要问题是如何让右侧块、下方块和底部块的检查工作起来。你能画个信息图表或类似的东西吗？我可以读懂代码，但不理解背后的想法。 - Florian p.i.

2

你的“不可达”是可达的，在sudoku被调用时，它将被触发，当网格完全填满时。此外，没有任何控制路径在首次调用自身之前返回true，这意味着唯一可能的输出结果是false和无限递归。 - sp2danny

哦，是的，你说得对，谢谢！我没有想到这种可能性。我会尝试修复它。 - Florian p.i.

-2

你需要一个栈。然后你需要彻底地尝试1-9，如果全部无效就回溯。如果1-9全部无效，你需要继续上一层，并且如果1-9全部无效再次回溯。

但这是一个无望的算法。虽然它最终可以解决简单的数独问题，但执行时间太长了。

- Malcolm McLean

我正在递归地一个一个地检查，将值从1到9按升序放入堆栈中。这样做有问题吗？ - Gyanshu

是的，您需要有一个位置i，并填满到该位置的所有方块。如果无法填充正方形，请从i中减去一个，用下一个有效位置填充它，并在i + 1处重新尝试。但这是一种不切实际的算法。您需要识别仅具有1或2个可能性的方块，这要复杂得多。 - Malcolm McLean

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- B. Decoster · Accepted Answer

重新修订的答案： 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）到右下角的任何矩形都包含有效填充。即您可以输入数字而不违反数独规则。计算的内容应该是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中的第二个或第三个布尔值时，您没有处理正确的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