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 conveniennt. Register | Membership benefits
 Get email delivery of the Custom IC Design blog (individual posts).

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

 Send yourself a copy

Subscribe

• RSS
Cadence RSS Feeds

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

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

 Send Yourself A Copy

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

Comments(0)

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.

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

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.

Performance Measurements
PuzzleAlgorithm 1
(seconds)
Algorithm 2
(seconds)
Comparison
< 1.0 is bad
(More is Better)
4-10.04200.06691 / 1.59 degradation
4-20.02300.08301 / 3.61 degradation
4-30.00300.02201 / 7.35 degradation
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

Leave a Comment

 Name E-mail (will not be published) Comment I have read and agree to the Terms of use and Community Guidelines.
 Community GuidelinesThe Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.
 About Cadence| Investor Relations| Careers| Terms of Use| Privacy Policy| US Trademarks © Cadence Design Systems, Inc. All Rights Reserved.