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

• In Part 1, we saw the rules of sudoku and a brief introduction to the SKILL++ Object System.
• In Part 2, we started solving the problem top-down by implementing the top level function SkuSolve and agreeing to fill in all the missing pieces incrementally until the program was complete. We also saw how to use hierarchical class definitions to represent the components representing rows, columns and 3x3 blocks.
• In Part 3, we saw how to create and initialize non-trivial instances of SKILL++ classes, and used these techniques to initialize the sudoku board with a given partial solution, ready for solving.
• In this posting, Part 4, we'll finally show one possible definition of function SkuFindSolution.

Just for a reminder, here is the definition of the top level function, SkuSolve.

(defun SkuSolve (partial_solution)
  (let ((sudoku (SkuInitialize (SkuNew) partial_solution)))
    (printf "starting with: \n%s\n"
            (SkuPrint sudoku))
    (printf "\nfound solution:\n%s\n"
            (SkuPrint (SkuFindSolution sudoku)))))

We have already seen the definitions of SkuNew, SkuInitialize, and SkuPrint. Now we can take a look at the implementation of SkuFindSolution, the function which actually searches for the sudoku solution.

The function SkuFindSolution takes an instance of class SkuSudoku (created by SkuNew, and populated by SkuInitialize) and modifies it to find a solution of the sudoku puzzle, assuming one exists.

How does it work?

It basically brute forces its way through the cells in the board, trying every possibility for each cell, from 1 to 9, which does not present an immediate conflict. If no solution exists for a particular cell (i.e., if each choice from 1 to 9 inflicts a conflict), the algorithm backtracks and tries a different guess, until it guesses correctly.

The local function conflict? asks "Does the given digit already exist in the row, column, or 3x3 block which contains the cell?" If not, it is a potentially valid guess. The local function solve_cells takes a list of all the remaining cells which have not yet been visited. Each digit that does not create a conflict is tried. There are three cases in the (cond ...):

1. If there are no more cells to consider, then we're done; we've found a solution! In this case we don't return from solve_cells, but rather return from (SkuFindSolution ...) thanks to prog/return.
2. If the cell already has a value in it, skip it because it was given in the puzzle partial solution. Note that this second case refuses to recure if a conflict is found. This means the puzzle has no solution, and recursion terminates, causing SkuFindSolution to return nil.
3. Otherwise, try all possibilities 1 through 9, skipping conflicts. If the (for ...) loop completes, that means we didn't find a solution for this cell. This happens if we've made an invalid guess in a previous iteration. So we set the cell back to the unsolved state (nil), and backtrack.

(defun SkuFindSolution (partial)
  (prog ()
    (labels ((conflict? (digit cell)
               (exists group '(column row b3x3)
                 (exists c (slotValue cell group)->cells
                   (and (neq c cell)
                        (eqv digit 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)))))
      (solve_cells sudoku->cells))))

Now you can test the program by copying the following into the CIWindow which comes from the Sudoku Wikipedia entry.

(SkuSolve '((5 3 ?  ? 7 ?  ? ? ?)
            (6 ? ?  1 9 5  ? ? ?)
            (? 9 8  ? ? ?  ? 6 ?)

            (8 ? ?  ? 6 ?  ? ? 3)
            (4 ? ?  8 ? 3  ? ? 1)
            (7 ? ?  ? 2 ?  ? ? 6)

            (? 6 ?  ? ? ?  2 8 ?)
            (? ? ?  4 1 9  ? ? 5)
            (? ? ?  ? 8 ?  ? 7 9)))

You should get the following result if you entered the code correctly.

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

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

If you notice, this algorithm only finds one solution of the sudoku puzzle. In some cases there are multiple solutions, but this algorithm won't find them. For example, the empty puzzle has lots of solutions.

(SkuSolve '((? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)

            (? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)

            (? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)
            (? ? ? ? ? ? ? ? ?)))

starting with: 
+-----------------+
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+-----------------+

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

The SkuSolve function is good at detecting that no solution exists for a particular puzzle.

(SkuSolve '((5 3 4  6 7 8  9 1 2)
            (6 7 2  1 9 5  3 4 8)
            (1 9 8  3 4 2  5 6 7)

            (8 5 9  7 6 1  4 2 3)
            (4 2 6  8 5 3  7 9 1)
            (7 1 3  9 2 4  8 5 6)

            (9 6 ?  5 3 7  2 8 4)
            (1 8 7  4 1 9  6 3 5)
            (? ? 5  2 8 6  1 7 9)))

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


no solution

In this posting, we have seen a fairly straightforward approach to solving the sudoku puzzle. The solution algorithm is pretty easy because the data structures representing the structure of the board make it easy to ask the questions we need to ask, such as:

• Is there a conflict putting a digit into a cell?
• Which row, column, and 3x3 block is a given cell in?
• Is a given cell pending resolution?

The particular implementation of SkuFindSolution also shows an example of how to use SKILL++ local functions. This usage avoids polluting the global function space.

In the next posting of SKILL for the Skilled we'll take a look at some shortcomings of this algorithm, particularly in regard to performance.

Jim Newton