Sudoku Solver

[Snaksa]

Hello! I'm trying to make a Sudoku Solver for a couple of days. I searched in Google and find that the best way is backtracking. But it seems that I don't understand how to implament the algorithm. When I run my program and it reaches a point where it must go back, it goes back only one time and increases the value of the cell with one. If it's still impossible the program stops. Here is the algorithm that I'm trying to implement:

start at the first empty cell, and put 1 in it.
Check the entire board, and see if there are any conflicts
If there are coflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
If the board is clean move, start at step one again.
If all nine possible numbers on a given cell cause a conflict in the board, then you set this cell back to empty, go back to the previous cell, and start again from step 3 (this is where the 'backtracking' comes in).

I'm trying to solve a completely empty sudoku until I see that my algorithm stops.

The output is:

1 2 3 | 4 5 6 | 7 8 9 |
------+-------+--------
4 5 6 | 1 2 9 | 3 0 0 |
------+-------+-------|
0 0 0 | 0 0 0 | 0 0 0 |
//And every cell till the end is 0....

This is my Solve function. Something is very wrong with the implementation of the algorithm that I gave above. Can you help me to find my mistake, because I'm trying for more than 3 days and nothing comes to my mind :/

void Sudoku::Help_Solve(int i, int j)
      {
        if(j == 10) j = 1, i = i+1;
        if(change[i][j] == 1) return Game.Help_Solve(i, j+1);
        else
          {
            int p = board[i][j] + 1;
            while(p <= 9)
              {
                if(Game.Check_Conflicts(p, i, j))
                  {
                    board[i][j] = p;
                    return Game.Help_Solve(i, j+1);                         
                  }      
                p++;
                if(p == 10) 
                  {
                    if(j == 1) j = 9, i = i-1;
                    return Game.Help_Solve(i, j-1);
                  } 
              }              
          }

[Lachlan Easton]

The lines 16-20 can go outside the while statement (underneath); when the while loop finishes p will equal 10, so there's no need for the if statement.
And while we're on the topic of that block, suppose j == 1, then line 18 sets j to 9. On the next line you pass j-1 (so 8) to Help_Solve, I'm assuming j is the current row, the rows seem to be ordered from 1 to 9, in that case j will go back one too many rows. You should also be using array indices 0 to 8, you may be getting subtle errors if the board is initialised [9][9].

[rapidcoder]

Backtracking-alone is very inefficient way of solving Sudoku. Sudoku is best solved by constraint-propagation with eventual little help of backtracking.

Read this awesome blog post by Peter Norvig here: http://norvig.com/sudoku.html

[Snaksa]

@Lachlan Easton, thanks for the advice - I will try it.

@rapidcoder, this example is explained in Python. Can you recommend me some article in C++?

[Snaksa]

I found a working code on the Internet and now everything is fine, but I can't understand it. If there are conflicts with all numbers between 1 and 9, the program should stop right? But it continues. Can somebody explain me how the code works, because I find some difficulties. Here is the code:

bool Sudoku::Help_Solve(int i, int j)
      {
        int nextrow, nextcol;
        while(change[i][j] == 1) //We find the first cell in which we can change the number
          {                      
            j++;
            if(j > 9)
              {
                j = 1;
                i++;     
              }     
            if(i > 9) return true;            
          }

          
        for(int p = 1; p <= 9; p++)
          {
            if(Game.Check_Conflicts(p, i, j)) //We are checking for conflicts
              {
                board[i][j] = p;
                nextrow = i;
                nextcol = j+1;    
                if(nextcol > 9)
                  {
                    nextcol = 1;
                    nextrow++;     
                  } 
                if(nextcol == 1 && nextrow == 10) return true; 
                if(Game.Help_Solve(nextrow, nextcol)) return true;                   
              }      
          }
        board[i][j] = 0;
        return false;
      }