Optimizing the backtracking algorithm solving Sudoku

Question

Hi,

I'm hoping to optimize my backtracking algorithm for my Sudoku Solver.

---

What it does now:

The recursive solver function takes a sudoku puzzle with various given values.

I will scour through all the empty slots in the puzzle, looking for the slot that has the least possibilities, get the list of values.

From the list of values, I will loop through it, by placing one of the values from the list in the slot, and recursively solve it, until the entire grid is filled.

---

This implementation still takes incredibly long for some puzzles and I hope to further optimize this, does anyone have any ideas how I might be able to further optimize this?

Thanks!

---

Heres my code in Java if your interested.

public int[][] Solve(int[][] slots) {
     // recursive solve v2 : optimization revision

     int[] least = new int[3];
     least[2] = Integer.MAX_VALUE;
     PuzzleGenerator value_generator = new PuzzleGenerator();
     LinkedList<Integer> least_values = null;

     // 1: find a slot with the least possible solutions
     // 2: recursively solve.

     // 1 - scour through all slots.
     int i = 0;
     int j = 0;
     while (i < 9) {
      j = 0;
      while (j < 9) {
       if (slots[i][j] == 0) {
        int[] grid_posi = { i, j };
        LinkedList<Integer> possible_values = value_generator
          .possibleValuesInGrid(grid_posi, slots);
        if ((possible_values.size() < least[2])
          && (possible_values.size() != 0)) {
         least[0] = i;
         least[1] = j;
         least[2] = possible_values.size();
         least_values = possible_values;
        }
       }
       j++;
      }
      i++;
     }

     // 2 - work on the slot
     if (least_values != null) {
      for (int x : least_values) {
       int[][] tempslot = new int[9][9];
       ArrayDeepCopy(slots, tempslot);
       tempslot[least[0]][least[1]] = x;

       /*ConsoleInterface printer = new gameplay.ConsoleInterface();
       printer.printGrid(tempslot);*/

       int[][] possible_sltn = Solve(tempslot);
       if (noEmptySlots(possible_sltn)) {
        System.out.println("Solved");
        return possible_sltn;
       }
      }
     }
     if (this.noEmptySlots(slots)) {
      System.out.println("Solved");
      return slots;
     }
     slots[0][0] = 0;
     return slots;
    }

Answer 1

You should probably use a profiler to see which statement is taking the most time, and then think about how to optimize that.

Without using a profiler, my suggestion is that you're creating a new PuzzleGenerator from scratch each time, and passing slots as an argument to the possibleValuesInGrid method. I think that means that PuzzleGenerator is recalculating everything from scratch each time, for each position and for each slots configuration; whereas instead it might be [much] more efficient if it remembered previous results and changed incrementally.

Answer 2

Do some constraint propagation before each nondeterministic step.

In practice this means that you have some rules which detect forced values and inserts them, and only if this doesn't make progress any more you resort to backtracking search through possible values.

Most Sudoku puzzles for humans are designed so that they don't need backtracking at all.

Answer 3

A while ago I implemented Donald Knuth's Dancing Links and his Algorithm X for Sudoku in Ruby (a language not known to be too efficient). For the few examples I checked, it took few milliseconds on my 1.5 GHz laptop.

You can look at the wikpedia how the Dancing Links work, and adapt it to Sudoku yourself. Or you take a look at "A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm".

PS: Algorithm X is a backtracking algorithm.

Answer 4

I think a big optimization would be to keep not only the state of the board, but for each row/col/square if it contains each of the numbers 1-9. Now to check if a position can have a number you simply need to check if the row/col/square the position is in don't contain that number (which is just 3 array lookups).

Also a big speed loss has to be making a new array for each recursive call. Instead of doing this make the change in the array before the recursive call, then undo it after the recursive call. Basically add the invariant that Solve will change slots while it runs, but when it returns it will leave it as it was when the function was called.

Also every time solve returns you have to check if the board is solved or not. If solve doesn't find a solution it should just return null, if it finds a solution it should return that. This way you can quickly test if your recursively call to solve found a solution or not.

Does placing a number in the square with the fewest options really help? Without that the code is a lot simpler (you don't have to save things in linked lists etc.)

Here is my psuedo code:

for(square on the board)
      for(possible value)
           if(this square can hold this value){
                place value on the board
                update that this row/col/square now contains this value

                recursive call
                if recursive call succeeded return the value from that call

                update that this row/col/square does not contain this value
                undo placing value on board
           }
if (no empty squares)
    return solved

Here is my code (I haven't tested it):

public int[][] solve(int[][] board, boolean[][] row, boolean[][] col, boolean[][] square){
 boolean noEmpty = true;
 for(int i = 0; i < 9;i++){
  for(int j = 0; j < 9;j++){
   if(board[i][j] == 0){
    noEmpty = false;
    for(int v = 1; v <= 9; v++){
     int sq = (i/3)*3+(j/3);
     if(row[i][v-1] == false && col[j][v-1] == false && square[sq][v-1] == false){
      board[i][j] = v;
      row[i][v-1] = true;
      col[j][v-1] = true;
      square[sq][v-1] = true;
      int[][] ans = solve(board,row,col,square);
      if(ans != null)
       return ans;
      square[sq][v-1] = false;
      col[j][v-1] = false;
      row[i][v-1] = false;
      board[i][j] = 9;
     }
    }
   }
  }
 }
 if(noEmpty){
  int[][] ans = new int[9][9];
  for(int i = 0; i < 9;i++)
   for(int j = 0; j < 9;j++)
    ans[i][j] = board[i][j];
  return ans;
 }else{
  return null;
 }  
}

Answer 5

Finding the slot with the least possible solutions is incredibly expensive, and for a traditional Sudoku puzzle probably isn't worth the overhead.

An easier optimization is to keep track of how many of each digit has been used, and when you "try" to place a digit in a slot, start with the one that has been used the least (edit: make sure to include the ones the puzzle was seeded with). This will make your algorithm more likely to start down a successful path rather than a failed one.

Also, do check out Artificial Intelligence: A Modern Approach as suggested by Imsasu. It is a fantastic book and covers recursive backtracking in good detail.

P.S. I'm curious as to the performance gains (if any) given by your "step 1" optimization. Do you have a figure?

Answer 6

Hi there, a long time I wrote a Sudoku solver (several years ago, but I keep all the code I write). It hasn't been generalized to solve "bigger" size than the usual Sudoku, but it is pretty fast.

It solves the following in 103 ms (on a Core 2 Duo 1.86 Ghz) and really hasn't been optimized:

        {0,0,0,0,7,0,9,4,0},
        {0,7,0,0,9,0,0,0,5},
        {3,0,0,0,0,5,0,7,0},
        {0,8,7,4,0,0,1,0,0},
        {4,6,3,0,0,0,0,0,0},
        {0,0,0,0,0,7,0,8,0},
        {8,0,0,7,0,0,0,0,0},
        {7,0,0,0,0,0,0,2,8},
        {0,5,0,2,6,8,0,0,0},            

How fast is yours and on which board is it slow? Are you sure you're not constantly revisiting path that shouldn't be revisited?

Here's the meat of the algo:

private static void solveRec( final IPlatform p ) {
    if (p.fullBoardSolved()) {
        solved = p;
        return;
    }
    boolean newWayTaken = false;
    for (int i = 0; i < 9 && !newWayTaken; i++) {
        for (int j = 0; j < 9 && !newWayTaken; j++) {
            if (p.getByteAt(i, j) == 0) {
                newWayTaken = true;
                final Set<Byte> s = p.avail(i / 3, j /3);
                for (Iterator<Byte> it = s.iterator(); it.hasNext();) {
                    final Byte b = it.next();
                    if (!p.columnContains(j, b) && !p.lineContains(i, b)) {
                        final IPlatform ptemp = duplicateChangeOne(p, b, i, j);
                        solveRec(ptemp);
                        if (solved != null) {
                            return;
                        }
                    }
                }
            }
        }
    }
}

And the IPlatform abstraction (please be nice, it was written a lot of years ago, before I knew that in Java adding 'I' before interface names wasn't all the rage):

public interface IPlatform {

    byte getByteAt(int i, int j);

    boolean lineContains(int line, int value);

    boolean columnContains(int column, int value);

    Set<Byte> avail(int i, int j);

    boolean fullBoardSolved();

}

Answer 7

I had an assignment to do just that: build the fastest sudoku solver in Java. I ended up winning the contest with a time of 0.3 millisecond.

I didn't use the dancing links algorithm and didn't compare with it, but some contestants must have tried it, yet my closest competitor took about 15 milliseconds.

I simply used a recursive backtracking algorithm, augmented it with 4 "rules" (which made backtracking unnecessary for almost every puzzle) and kept a bit field as a list of legal values for each position.

I wrote a blog post about it and posted the code here : http://www.byteauthor.com/2010/08/sudoku-solver/