Optimizing the backtracking algorithm solving Sudo

Question

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, and 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?

---

Here's my code in Java if you're 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

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 2

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 3

The results from my optimizations of the backtracking algorithm for Sudoku are below. You can download the code from http://yikes.com/~bear/suds.c. This is purely based on pigeon hole principle and I found it to generally be faster than rules based solving.

Using the values from another post on this thread I get a result of 7ms on a core2 duo @2.2 ghz or 3ms on a core i5. This compares to the poster's result of 100ms, although that may have been measured in a different way. Timing added in http://yikes.com/~bear/suds2.c.

I wrote this 10 years ago, and would certainly optimize in a different way if I re-did this problem.

$ ./a.out 000070940070090005300005070087400100463000000000007080800700000700000028050268000
[----------------------- Input  Data ------------------------]

*,*,*   *,7,*   9,4,*   
*,7,*   *,9,*   *,*,5   
3,*,*   *,*,5   *,7,*   

*,8,7   4,*,*   1,*,*   
4,6,3   *,*,*   *,*,*   
*,*,*   *,*,7   *,8,*   

8,*,*   7,*,*   *,*,*   
7,*,*   *,*,*   *,2,8   
*,5,*   2,6,8   *,*,*   

[------------------ Solution 01 -------------------]

2,1,5   8,7,6   9,4,3   
6,7,8   3,9,4   2,1,5   
3,4,9   1,2,5   8,7,6   

5,8,7   4,3,2   1,6,9   
4,6,3   9,8,1   7,5,2   
1,9,2   6,5,7   3,8,4   

8,2,6   7,4,3   5,9,1   
7,3,4   5,1,9   6,2,8   
9,5,1   2,6,8   4,3,7   

Time: 0.003s Cyles: 8619081