Cadence.com will be under maintenance from Friday, Oct. 3rd at 6pm (PST) thru Sunday, Oct 5th at 11pm (PST).
Home > Community > Blogs > Custom IC Design > u nder construction skill for the skilled introduction to classes part 5

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

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.

Sudoku puzzle 5-1
`(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))`
and to insert a call to `(sort ... (genCmpFunction...))`
`sudoku->cells = (sort sudoku->cells                      (genCmpFunction ?key count_possibilities))`
before calling `solve_cell`.

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

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.

Performance Measurements
PuzzleAlgorithm 1
(seconds)
Algorithm 2
(seconds)
Comparison
(More is Better)
5-125.222.07512.154 improvement

Summary

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