0

I was trying to wrote a Sudoku solver algorithm, it should work like this: Pick a blank space, Choose a number and verify if is possible to have that number in that spot, if not choose another number, Recursively try to find a solution and if there are no possible backtrack until you find one. the problem is that this print absolutely nothing, i don't know what to do pls help.

#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);
}
ASDF12345QWERTY
  • 1
  • 5
    *i don't know what to do pls help.* -- [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – PaulMcKenzie Mar 02 '20 at 20:22
  • 1
    What is the input? – miszcz2137 Mar 02 '20 at 20:24
  • ***the problem is that this print absolutely nothing, i don't know what to do*** Use your debugger to figure out why. Specifically does it loop forever or does it just not find a solution when the input is valid. – drescherjm Mar 02 '20 at 20:25
  • 1
    You might also, besides debugging which is the best place to start, put `std::cout` for information in your `solve(...)` Also: [Why should I not #include ](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is “using namespace std;” considered bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – lakeweb Mar 02 '20 at 20:30
  • The program exits without printing anything because your back tracking doesn't work and it exits early. Starting with `000000200,080007090,602000500,070060000,000901000,000020040,005000603,090400070,006000000` the solve() gets to x=3,y=1 on `957643281,483107090,602000500,070060000,000901000,000020040,005000603,090400070,006000000` and tries every number - none of them fit so it returns all the way up and exits the program. – Jerry Jeremiah Mar 02 '20 at 21:39
  • Have a look at the recursion output here https://onlinegdb.com/B1YSQ-jV8 and see if you can figure out why it exits early. – Jerry Jeremiah Mar 02 '20 at 22:01

2 Answers2

0

It never prints a solution for a simple reason.

It is too slow and never finds one. You may see something before heat death of the universe but no guarantees.

miszcz2137
  • 894
  • 6
  • 18
0

While you don't see anything on the output is the problem you are facing, I believe the main problem is that your solve is not right and it definitely has the potential to recurse infinitely.

In your solve you need to first check if there are any cells that can be filled and then you go to doing the actual work. Without that check first you end up in doing the same work again and again.

The right way is:

  1. Check if there is any cell that can be filled, get its i, j
  2. If no, exit
  3. If yes, choose a number from 1 to 9 and see if its possible to fill the location i,j with that number.
  4. Then check if there is any cell again that needs to be filled.
  5. If no cells, you are done.
  6. If cells are still present, unchoose the number
  7. Go to next choice.
SomeDude
  • 13,876
  • 5
  • 21
  • 44