Optimizing the backtracking algorithm solving Sudoku

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;
}

---

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/

---

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();

}

---

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.

链接地址: http://www.djcxy.com/p/96154.html

上一篇: Sudoku的逻辑解算算法（Java）

下一篇: 优化解决Sudoku的回溯算法