- 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.

**Solving the sudoku puzzle**

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
...)
```

:

- 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`

. - 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`

. - 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))))

**Testing the program**

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

Sudoku puzzle 4-1 |
---|

(SkuSolve '((5 3 ? ? 7 ? ? ? ?) |

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.

Sudoku puzzle 4-2 |
---|

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

+-----------------+

**What if there is no solution?**

The `SkuSolve`

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

Sudoku puzzle 4-3 |
---|

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

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

**Summary**

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.

**Preview**

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