Почему этот алгоритм "Судоку Солвер" не работает

Question

Я пытался написать алгоритм решения судоку, он должен работать следующим образом: выбрать пробел, выбрать число и проверить, возможно ли иметь это число в этом месте, если не выбрать другое число, рекурсивно попытаться найти решение, и если нет возможности вернуться назад, пока вы не найдете его. проблема в том, что эта печать абсолютно ничего, я не знаю, что делать, пожалуйста, помогите.

#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

Хотя вы ничего не видите на выходе, это проблема, с которой вы сталкиваетесь, но я считаю, что главная проблема в том, что ваш solve не прав, и он определенно может бесконечно повторяться.

В вашем solve вы должны сначала проверить, есть ли какие-либо ячейки, которые можно заполнить, а затем вы go выполняете фактическую работу. Без этой проверки сначала вы снова и снова выполняете одну и ту же работу.

Правильный путь:

1. Проверьте, есть ли ячейка, которая может быть заполнена, получите ее i , j
2. Если нет, выйдите из
3. Если да, выберите число от 1 до 9 и посмотрите, возможно ли заполнить местоположение i, j этим числом.
4. Затем проверьте, есть ли еще ячейки, которые нужно заполнить.
5. Если ячеек нет, все готово.
6. Если ячейки еще присутствуют, выберите следующий номер:
7. Go.

Answer 2

Оно никогда не печатает решение по простой причине.

Это слишком медленно и никогда его не находит. Вы можете увидеть что-то до тепловой смерти вселенной, но никаких гарантий.