Sudoku Solver by Backtracking question update

Question

Assuming a two dimensional array holding a 9x9 sudoku grid, where is my solve function breaking down? I'm trying to solve this using a simple backtracking approach. Thanks!

bool solve(int grid[9][9])
{
 int i,j,k;
 bool isSolved = false;

  if(!isSolved(grid))
   isSolved = false;

  if(isSolved)
   return isSolved;

  for(i=0; i<9; i++)
  {
   for(j=0; j<9; j++)
   {
    if(grid[i][j] == 0)
    {
     for(k=1; k<=9; k++)
     {
      if(legalMove(grid,i,j,k))
      {
       grid[i][j] = k;
       isSolved = solve(grid);
       if (isSolved)
        return true;
      }
      grid[i][j] = 0;
     }
     isSolved = false;
    }
   }
  }

return isSolved;
}

Even after changing the 'isSolved' issues, my solution seems to breakdown into an infinite loop. It appears like I am missing some base-case step, but I'm not sure where or why. I have looked at similar solutions and still can't identify the issue. I'm just trying to create basic solver, no need to go for efficiency. Thanks for the help!

Answer 1

You refer to isSolved as both a function and a boolean variable. I don't think this is legal, and its definitely not smart.

Your functions should have distinct names from your variables.

Answer 2

It seems that regardless of whether or not it is a legal move, you are assigning "0" to the square, with that "grid[i][j] = 0;" line. Maybe you meant to put "else" and THEN "grid[i][j] = 0;" ?

Answer 3

Yea your base case is messed up. In recursive functions base cases should be handled at the start. You got

bool isSolved = false;

if(!isSolved(grid))
    isSolved = false;

if(isSolved)
    return isSolved;

notice your isSolved variable can never be set to true, hence your code

if(isSolved)
    return isSolved;

is irrelevant.

Even if you fix this, its going to feel like an infinite loop even though it is finite. This is because your algorithm has a possible total of 9*9*9 = 729 cases to check every time it calls solve. Entering this function n times may require up to 729^n cases to be checked. It won't be checking that many cases obviously because it will find dead ends when placement is illegal, but whose to say that 90% of the arragements of the possible numbers result in cases where all but one number fit legally? Moreover, even if you were to check k cases on average where k is a small number (k<=10) this would still blow up (run time of k^n.)

The trick is to "try" placing numbers where they will likely result in a high probability of being the actual good placement. Probably the simplest way I can think of doing this is a constraint satisfaction solver, or a search algorithm with a heuristic (like A*.)

I actually wrote a sudoku solver based on a constraint satisfaction solver and it would solve 100x100 sudokus in less than a second.

If by some miracle the "brute force" backtracking algorithm works well for you in the 9x9 case try higher values, you will quickly see a deterioation in run time.

I'm not bashing the backtracking algorithm, in fact I love it, its been shown time and time again that backtracking if implemented correctly is far more efficient than "dynamic programming", however, in your case you aren't implementing it correctly. You are bruteforcing it, you might as well just make your code non-recursive, it will accomplish the same thing.