Cadence.com will be under maintenance from Friday, Oct. 3rd at 6pm (PST) thru Sunday, Oct 5th at 11pm (PST).
Cadence.com login, registration, community posting and commenting functionalities will be disabled.
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

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

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

Comments(0)Filed under: Custom IC Design, Virtuoso, SKILL, Team SKILL, programming, LISP, SKILL++, object orientation, Sudoku

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

SKILL for the Skilled: Introduction to Classes - Part 1
SKILL for the Skilled: Introduction to Classes - Part 2
SKILL for the Skilled: Introduction to Classes - Part 3
SKILL for the Skilled: Introduction to Classes - Part 4

Comments(0)

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