Sudoku algorithm with backtracking - java

Question

So I have this university assignment to solve Sudoku... I read about Algorithm X and Dancing algorithm, but they didn't help me.

I need to make it with backtracking. I hard-coded some of the indexes in the two dimensional array with numbers on places given from Wikipedia (so I am sure that it's solvable).

The code I got is the following:

public void solveSudoku(int row, int col)
   {
      // clears the temporary storage array that is use to check if there are
      // dublicates on the row/col
      for (int k = 0; k < 9; k++)
      {
         dublicates[k] = 0;
      }
      // checks if the index is free and changes the input number by looping
      // until suitable
      if (available(row, col))
      {
         for (int i = 1; i < 10; i++)
         {
            if (checkIfDublicates(i) == true)
            {
               board[row][col] = i;
               if (row == 8)
                  solveSudoku(0, col + 1);
               else if (col == 8)
                  solveSudoku(row + 1, 0);
               else
                  solveSudoku(row, col + 1);

               board[row][col] = 0;
            }
         }
      }
      // goes to the next row/col
      else
      {
         if (row == 8)
            solveSudoku(0, col + 1);
         else if (col == 8)
            solveSudoku(row + 1, 0);
         else
            solveSudoku(row, col + 1);
      }
   }

   /**
    * Checks if the spot on the certain row-col index is free of element
    * 
    * @param row
    * @param col
    * @return
    */
   private boolean available(int row, int col)
   {
      if (board[row][col] != 0)
         return false;
      else
         return true;
   }

   /**
    * Checks if the number given is not already used in this row/col
    * 
    * @param numberToCheck
    * @return
    */
   private boolean checkIfDublicates(int numberToCheck)
   {
      boolean temp = true;
      for (int i = 0; i < dublicates.length; i++)
      {
         if (numberToCheck == dublicates[i])
         {
            temp = false;
            return false;
         }
         else if (dublicates[i] == 0)
         {
            dublicates[i] = numberToCheck;
            temp = true;
            return true;
         }
      }
      return temp;
   }

I am getting StackOverflow on

// goes to the next row/col
          else
          {
             if (row == 8)
                solveSudoku(0, col + 1);
             else if (col == 8)
                solveSudoku(row + 1, 0);
             else
                solveSudoku(row, col + 1);
          }

which means that I have to stop the recursion at some point, but I can't figure it out how! If you find any other mistakes in the solve() function - let me know. Because I am not sure I understand the "backtracking" thing completely...

Romberg

byteauthor.com/2010/08/sudoku-solver has nice example about this. – Impotence

Wiki too ;) – Chane

You should look at your dublicates code. I don't see how this could check if a number is allowed. You always reset it (with each SolveSudoku call) so it forgets everything. I also have my doubts on how an array of 9 elements can check everything – Sisley

Answer 1

You can stop recursion for example if you keep track of the current recursion depth

public void solveSudoku(int row, int col, int recursionDepth) {
    // get out of here if too much
    if (recursionDepth > 15) return;

    // regular code...
    // at some point call self with increased depth
    solveSudoku(0, col + 1, recursionDepth + 1);
}

---

And if you find any other mistakes in the solve() function - let me know.

Too much code :)

Tobias

Answer 2

This is roughly the way I've done this in the past.

Whenever all the definite moves have been taken and there is a choice of equally good next moves:
    copy your grid data structure and push it onto a stack.
    take the first candidate move and continue solving recursively
    Whereever you get stuck:
         pop the saved grid off the stack
         take the next candidate move.

Heydon

Answer 3

I made it in a more simple way:

public void solve(int row, int col)
   {
      if (row > 8)
      {
         printBoard();
         System.out.println();
         return;
      }
      if (board[row][col] != 0)
      {
         if (col < 8)
            solve(row, col + 1);
         else
            solve(row + 1, 0);
      }
      else
      {
         for (int i = 0; i < 10; i++)
            if (checkRow(row, i) && checkCol(col, i))
                  //&& checkSquare(row, col, i))
            {
               board[row][col] = i;
               if (col < 8)
                  solve(row, col + 1);
               else
                  solve(row + 1, 0);
            }
         board[row][col] = 0;
      }
   }

   private boolean checkRow(int row, int numberToCheck)
   {
      for (int i = 0; i < 9; i++)
         if (board[row][i] == numberToCheck)
            return false;

      return true;
   }

   private boolean checkCol(int col, int numberToCheck)
   {
      for (int i = 0; i < 9; i++)
         if (board[i][col] == numberToCheck)
            return false;

      return true;
   }

Romberg

Answer 4

I'm not sure why you say that Dancing Links and Algorithm X were not useful.
Do you mean that you were not able to map Sudoku to an instance of the Exact Cover problem that Algorithm X is designed to solve?
Or that it is a too complicated approach for what you need??

If the former is the case, you might want to look at: A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm. It's quite clear and explains also the reasoning behind.

N.B. Algorithm X is a backtracking algorithm so, if that's your only requirement, you can definitely use this approach.

Hope this can help.

Apanage

Well, I didn't say that Dancing Links and Algorithm X are not useful. I said that I couldn't really understand them so I couldn't use them. But I will read what's written in the link you gave me. Thanks ;) – Romberg