为什么此“ Sudoku求解器”算法不起作用

Question

我正在尝试编写Sudoku求解器算法，它应该像这样工作：选择一个空格，选择一个号码，并验证是否有可能在该地点使用该号码，如果不选择其他号码，递归地尝试找到一种解决方案，如果没有找到可能的解决方法，那么直到找到解决方案为止。问题是此打印绝对没有，我不知道该怎么做。

#include<bits/stdc++.h>

using namespace std;

bool possible(int y,int x,int n,int grid[9][9]){
    for(int i=0;i<9;i++){
        if(grid[y][i]==n)
            return false;
    }
    for(int i=0;i<9;i++){
        if(grid[i][x]==n)
            return false;
    }

    int y0 = y/3;
    int x0 = x/3;

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(grid[y0+i][x0+j]==n)
                return false;
        }
    }

    return true;

}

void display(int grid[9][9]){
    for(int y=0;y<9;y++){
        for(int x=0;x<9;x++){
            cout<<grid[y][x]<<" ";
        }   
        cout<<endl;
    }
}

void solve (int grid[9][9]){
    for(int y=0;y<9;y++){
        for(int x=0;x<9;x++){
            if(grid[y][x]==0){
                for(int n=1;n<10;n++){
                    if(possible(y,x,n,grid)){
                        grid[y][x] = n;
                        solve(grid);
                        grid[y][x] = 0;
                    }
                }
                return;
            }
        }   
    }
    display(grid);
}

int main(){
    int grid[9][9];
    ifstream in ("input.txt");
    for(int y=0;y<9;y++){
        for(int x=0;x<9;x++){
            in>>grid[y][x];
        }
    }
    solve(grid);
}

Answer 1

出于简单原因，它从未打印出解决方案。

它太慢了，永远找不到。在宇宙热死之前，您可能会看到一些东西，但没有保证。

Answer 2

虽然您在输出中看不到什么是您所面临的问题，但我认为主要的问题是您的solve不正确，并且绝对有可能无限递归。

在solve中，您需要先检查是否可以填充任何单元格，然后再进行实际工作。如果没有该检查，您最终将一次又一次地进行相同的工作。

正确的方法是：

1. 检查是否有任何可填充的单元格，获取其i，j
2. 如果否，退出
3. 如果是，请从1到9之间选择一个数字，并查看是否可以用该数字填充位置i，j。
4. 然后检查是否再次需要填充任何单元格。
5. 如果没有单元格，则完成。
6. 如果仍然存在单元格，请选择数字
7. 转到下一个选择。