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

Register | Membership benefits
Get email delivery of the Cadence 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 4

Comments(0)Filed under: Custom IC Design, Virtuoso, SKILL, Team SKILL, programming, LISP, SKILL++, object orientation, Sudoku 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

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.