SKILL for the Skilled: Introduction to Classes -- Part 5

In the previous SKILL for the Skilled postings, we looked at a pretty good algorithm for solving the Sudoku puzzle. This algorithm is able to find at least one solution of the puzzle if one exists, and is able to detect that no solution exists if that is in fact the case. In this article we look at a particularly difficult case which the algorithm we have chosen performs poorly.

What about a difficult puzzle?

In his article Solving Every Sudoku Puzzle, Peter Norvig suggests a puzzle which is pretty difficult. In fact it is the worse case for the algorithm he proposes in the article.

(SkuSolve '((? ? ?  ? ? 6  ? ? ?)
            (? 5 9  ? ? ?  ? ? 8)
            (2 ? ?  ? ? 8  ? ? ?)

            (? 4 5  ? ? ?  ? ? ?)
            (? ? 3  ? ? ?  ? ? ?)
            (? ? 6  ? ? 3  ? 5 4)

            (? ? ?  3 2 5  ? ? 6)
            (? ? ?  ? ? ?  ? ? ?)
            (? ? ?  ? ? ?  ? ? ?)))

The algorithm implemented in SkuFindSolution does in fact solve this puzzle but considerably slower than the other examples shown above. On the particular machine I'm using, all the puzzles described in the previous posting are solved in less than 1/10 of a second. This problematic puzzle takes more than 25 seconds to solve.

starting with: 
+-----+-----+-----+
| | | | | |6| | | |
| |5|9| | | | | |8|
|2| | | | |8| | | |
| |4|5| | | | | | |
| | |3| | | | | | |
| | |6| | |3| |5|4|
| | | |3|2|5| | |6|
| | | | | | | | | |
| | | | | | | | | |
+-----+-----+-----+


found solution:
+-----+-----+-----+
|8|3|4|9|7|6|5|1|2|
|6|5|9|2|3|1|7|4|8|
|2|7|1|4|5|8|6|9|3|
|1|4|5|8|6|2|3|7|9|
|7|2|3|5|4|9|8|6|1|
|9|8|6|7|1|3|2|5|4|
|4|1|7|3|2|5|9|8|6|
|5|9|2|6|8|4|1|3|7|
|3|6|8|1|9|7|4|2|5|
+-----+-----+-----+

A different algorithm

The version of SkuFindSolution shown in SKILL for the Skilled: Part 4 iterates over the cells in the board simply in the order they appear in the list. The following improved version of SkuFindSolution first sorts the cells into order of increasing possibility. Cells which have few possibilities are moved to the beginning of the list, and cells with more possibilities are moved to the end of the list.

The changes in the function are to introduce the local function count_possibilities into the (labels ...),

(count_possibilities (cell)
  (let ((c 0))
    (for i 1 9
      (unless (conflict? i cell)
        c++))
     c))

sudoku->cells = (sort sudoku->cells
                      (genCmpFunction ?key count_possibilities))

Recall the functions genCmpFunction and identity from a previous blog posting.

(defun genCmpFunction (@key (test lessp)
                            (key  identity))
  (lambda (A B)
    (test (key A)
          (key B))))

(defun identity (x)
  x)

The genCmpFunction generates a function which can be used as the second argument of sort. In this case genCmpFunction returns a function which will cause sort to order the cells in increasing order according to the return value of count_possibilities.

The local function count_possibilities returns the integer corresponding to how many of the number in the set {1 2 3 4 5 6 7 8 9} are conflict-free when placed in the given cell.

New version of SkuFindSolution

(defun SkuFindSolution (sudoku)
  (prog ()       
    (labels ((count_possibilities (cell)
               (let ((c 0))
                 (for i 1 9
                   (unless (conflict? i cell)
                     c++))
                 c))
             (conflict? (solution cell)
               (exists group '(column row b3x3)
                 (exists c (slotValue cell group)->cells
                   (and (neq c cell)
                        (eqv solution c->value)))))
             (solve_cells (cells)
               (cond
                 ((null cells)
                  (return sudoku))
                 (((car cells)->value)
                  (and (not (conflict? (car cells)->value
                                       (car cells)))
                       (solve_cells (cdr cells))))
                 (t
                  (let ((cell (car cells)))
                    (for solution 1 9
                      (unless (conflict? solution cell)
                        cell->value = solution
                        (solve_cells (cdr cells))))
                    cell->value = nil)))))
      
      sudoku->cells = (sort sudoku->cells
                            (genCmpFunction ?key count_possibilities))
      
      (solve_cells sudoku->cells))))

What about the performance?

I ran the new algorithm and the old algorithm on four examples, three from the previous posting 4-1, 4-2, and 4-3, and also on 5-1 above. It turns out that the old algorithm performs 2x to 8x faster than the new for the cases it handles well. In particular, for cases for which the old algorithm solves the puzzle in less than 1/10 of a second, the new algorithm works slower but still solves in less than 1/10 of a second. On the other hand, on the extreme case where old algorithm handles poorly, where the old algorithm requires half a minute to solve the puzzle, the new algorithm is 12x faster.

In this series of 5 postings (first four listed below) we've used the SKILL++ Object System to implement a sudoku puzzle solver.

I hope you will find the examples in these posting useful.

Jim Newton

SKILL for the Skilled: Introduction to Classes - Part 1
SKILL for the Skilled: Introduction to Classes - Part 2
SKILL for the Skilled: Introduction to Classes - Part 3
SKILL for the Skilled: Introduction to Classes - Part 4