Home > Community > Blogs > Custom IC Design > under construction skill for the skilled introduction to classes part 4

 Login with a Cadence account. Not a member yet? Create a permanent login account to make interactions with Cadence more convenient. Register | Membership benefits
 Get email delivery of the Custom IC Design blog (individual posts).

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

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

Comments(0) In several previous postings we introduced the problem of solving the sudoku puzzle.
• 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 ...)```:

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

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