Custom IC Design

Things You Didn't Know About Virtuoso: Rapid Adoption Kits

stacyw — Tue, 22 May 2012 23:26:00 GMT

This post isn't directly about tips and tricks for getting the most out of Virtuoso, but it is about a new source of information and hands-on guidance to help you put those tips and tricks into action.

They're called Rapid Adoption Kits, or--to use the obligatory Three Letter Acronym (TLA)--RAKs.

What is a Rapid Adoption Kit?

RAKs are collateral packages for a particular product area or flow which are designed to help you learn to use the tools as quickly and efficiently as possible. They center around a hands-on workshop database with a step-by-step manual so you can dive right in and start pushing buttons. They're easy to set up and let you move at your own pace.

Depending on the subject, other material may be included, such as videos or application notes.

Where can you find them?

Go to http://support.cadence.com and select Resources->Rapid Adoption Kits from the menus at the top. For Virtuoso, click on Virtuoso Custom IC and Sign-off Flow.

What's available?

As of today, there are 3 RAKs available.

Layout Design in IC 6.1.5

This material highlights new features and explores some basic functionality with Virtuoso Schematic Editor L/XL and Virtuoso Layout Suite L/XL in the 6.1.5 release. You will take a design from concept through implementation and learn how Virtuoso 6.1.5 capabilities can help you generate designs more efficiently

IC 6.1.5 Constraint Driven Custom Design

What you will learn: Use the Constraint Management System; use the Circuit Prospector for assisted constraint capture; verify constraints to ensure that design intent is met in layout; use the module generation (MODGEN) capability for precision Pcell-based array generation; perform constraint-driven wire editing; perform constraint-aware editing; perform special net automated routing (differential pair, shielding, etc.); perform full custom/analog placement.

Virtuoso Visualization & Analysis (ViVA)

What you will learn: View, configure, and export design data in a variety of formats quickly and easily; interactively analyze and annotate waveform data for design documentation; create and evaluate complex mathematical expressions, and save them for later reuse; how to efficiently handle gigabyte transient data files.

More Rapid Adoption Kits will be rolling out as time goes on. Give one a spin and let us know what you think!

Stacy Whiteman

Things You Didn't Know About Virtuoso: Change is Here to Stay

stacyw — Thu, 05 Apr 2012 13:00:00 GMT

Speaking of variation -- and isn't everyone these days -- something strikes me in reading about all the powerful and elegant features of corners management and statistical analysis. After all the simulations are run and the results are presented, unless you've managed to hit a bullseye on the first design you tried (good luck with that), you're probably going to have to change something in the circuit in order to turn all those lights green. (Of course, you'll only see that lovely green coloring --or the not-so-desirable yellow and red coloring--if you're using specifications in ADE XL).

We'll talk in a later article about the features that will help you figure out what circuit values to change. Today I want to focus on how to change them.

You could use the brute force method -- select devices on the schematic, edit their values, save the schematic, then resimulate. It's fairly tedious and you have no record of what combinations you've tried. I'll bet you're jotting down notes on little pieces of paper to keep track, aren't you?

Or you could get a bit fancier and edit the schematic to assign design variables to critical device properties. That allows you to change those variable values from within ADE XL using all its different analysis types. A very useful approach, but you still have to edit the schematic to set everything up and then edit it again once you've settled on the correct device values.

Which brings me to the subject of this article -- an Extremely Useful Feature in ADE XL which is also, sadly, one of the least known. ADE XL allows you to change the values of device instance parameters without having to edit the schematic. You can then easily run sweeps and corner simulations, do sensitivity analysis and circuit optimization without touching your schematics. And ADE XL's simulation history enables you to keep track of what experiments you've tried and what the results were. And yes, it takes care of triggering the callbacks at the appropriate time so the netlist is accurate.

Let's take a look at how to do this...

Creating Parameters

Parameters are created using the Variables and Parameters Assistant (VPA). Because the parameters are associated with device instance properties, you need open the VPA from a schematic. Start with an ADE XL setup, then use either File->Open... or RMB->Open Design in Tab on the test name in the Data View Assistant (and possibly descend the hierarchy) to get to the schematic containing the devices whose values you want to vary. Now open the Variables and Parameters Assistant.

Devices you select in the schematic will show up in the top half of the VPA with their editable CDF properties. Select one or more of these properties -- for example, length and finger width -- and RMB->Create Parameter. At the bottom of the VPA (and in the Parameters section of the Data View Assistant), you'll see something that looks like "M7/l" and "M7/fw". If you hover over them, you can see that it keeps track of the library/cellname/view of the schematic they come from (in case you parameterize "M7" in multiple blocks). These can now be treated just like any other variables.

You can change their values. You can assign them a list of values (1u,2u,3u) or a range of values (1u:1u:10u) to perform a sweep. You can access them in the Corners UI to change their values in corners simulations. You can use them in Sensitivity Analysis to better understand their impact on each circuit specification. You can use Global or Local Optimization to vary the values in order to find a design that meets all your specs across corners.

Parameter Relationships

The VPA also has 2 buttons at the top that let you create matching and ratio relationships between parameters. Simply select the devices in the schematic, expand one of them in the top part of the VPA, select the properties you want to be matched amongst the devices, and click the "Match Parameters" button at the top (sort of looks like 2 blue boxes with a red equals sign between them). In the bottom section of the VPA, you will see that one device will have a value (e.g. M7/fw = 2u) and the other(s) will be matched to it (e.g. M6/fw = M7/fw@ ). Now you only have to vary the value on one device and the others will vary with it.

Similarly, the "Ratio Matched Parameters" button (looks like "1:n") will create a ratioed relationship based on the lowest value.

What's Next?

Once you start using these handy parameterization techniques, you can quickly find yourself awash in results from all your "what-if" simulations. Next time, I'll talk about some convenient ways of managing all these different sets of parameter values.

For now, we'll skip ahead to the ultimate goal of this whole exercise -- you've found a circuit design that meets all your specifications across all the required corner and statistical conditions. Hooray! Now, it's time to edit your schematic to capture those golden device values. But you don't have to manually edit the properties of each transistor to do that. Just look at the ADE XL Result panel and find those good simulation results (it's easy--they're the ones that are all green!). Now RMB->click on the grey line just above those results and select Backannotate. The values will be written back to the appropriate devices on the schematic, including any matching or ratioing relationships you had made, and triggering any relevant callbacks.

For More Information

Details about how to create and work with device instance parameterization can be found in the ADE XL User Guide, the ADE XL Quick Start and this video.

Stacy Whiteman

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

Team SKILL — Fri, 10 Feb 2012 14:00:00 GMT

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
Puzzle	Algorithm 1 (seconds)	Algorithm 2 (seconds)	Comparison < 1.0 is bad (More is Better)
4-1	0.0420	0.0669	1 / 1.59 degradation
4-2	0.0230	0.0830	1 / 3.61 degradation
4-3	0.0030	0.0220	1 / 7.35 degradation
5-1	25.22	2.075	12.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

Things You Didn't Know About Virtuoso: Measurements Across Corners

stacyw — Thu, 09 Feb 2012 20:56:00 GMT

In Virtuoso IC 6.1.5 ISR6, we released a new feature in ADE XL, which had been requested by many customers--the ability to define a measurement expression which operates on the results of another measurement expression across corners. For example, I can create an expression to measure, say, a delay. Call it "myDelay". Now I can create another expression which calculates, for example, the maximum value of "myDelay" over all the corners I ran.

To do this, I simply add an expression in the ADE XL Outputs Setup pane, give it a name (optional), and set the cyclic in the "EvalType" column (you were wondering what that new column was for, weren't you?) to "corners". The line will now be highlighted in blue to distinguish it from regular waveform and scalar expressions. Now create your expression. If you use the functions ymax, ymin, average, peakToPeak or stddev, the argument "?overall t" will automatically be added to the function to ensure the values are treated by the function as discrete, rather than continuous points.

It should be fairly obvious what the above functions do--you run a simulation over corners and you can find the max, min, average, spread (peakToPeak), and stddev of any scalar measurement over those corners.

ymax(myDelay)
ymin(myDelay)
average(myDelay)
peakToPeak(myDelay)
stddev(myDelay)

Perhaps not so obvious is the fact that you can use other functions to measure across corners as well. For example, if you create a set of corners as a temperature sweep (remember, the definition of corners in ADE XL isn't restricted to PVT--you can create a variable out of pretty much anything and then sweep it in the Corners form), you can create a MAC expression using the cross() function to find the temperature at which an expression reaches a certain value:

cross(myDelay 200n 1 "either" nil nil)

Or you can use the value() function to find the value of an expression at an interpolated temperature value (or whatever variable you swept in your corners run):

value(myDelay 65)

MAC expressions are also supported for Monte Carlo analysis and Local and Global Optimization.

I'm sure you'll find this new feature useful. As always, comments and feedback are welcome!

Stacy Whiteman

Things You Didn't Know About Virtuoso: We've Got You Cornered

stacyw — Thu, 26 Jan 2012 17:26:00 GMT

One of the big buzzwords around the EDA world these days is "variation." Don't you just love buzzwords? Take a perfectly normal, slightly ambiguous word, capitalize it, add a another slightly ambiguous hyphenated suffix, and suddenly you've just solved a new problem for your customers. "Interface-driven'' "user-centric'', "platform-based" and "variation-aware."

Well, I'm not here to sling buzzwords. I'm here to help you find ways to make better use of our software so you can deal with the actual situations you have to face every day. And, of course, "variation" does exist. It exists in all sorts of forms in all parts of the design process. So today, let's talk about one of the most basic forms of variation you've been dealing with in design for years. Corners.

Specifically, I'd like to cover some of the features in Virtuoso IC6.1.5 which help you set up and run the massive number of corner combinations you have to define to verify your designs today.

First, it helps to realize that our definition of a "corner" can encompass any sort of variation you can define in ADE XL. It's not just limited to your classic PVT. You can create corners using any design variables, device parameters (to be the subject of a future article), or combination thereof. You can even create statistical corners based on sample points from Monte Carlo analysis (yet another future article).

The ability to create corners in many different ways opens the door to lots of efficient methods of circuit analysis.

But first, you've got to set them up.

If you're using IC6.1.5, you'll have noticed that we redesigned the Corners Setup UI. The basics of using the new form are covered in this video and this video. (And, of course, in the documentation.) The videos explain how to create corners, model groups and corner groups, as well as how to copy corners and enable or disable individual corners and corner groups for each simulation testbench.

Instead of repeating those topics here (you can always just watch the videos), I'll introduce some new features that have been added in recent ISR releases of IC6.1.5. Everything described here is available in ISR6 (released in Sept. 2011) or later.

Selective Corner Group Expansion

Rather than just expanding a group of corners completely, such that each column contains only one combination of values, you can now expand a corner group based on one or more selected parameters. There are 2 options for this. The first is similar to the original full corner group expansion, only you use just a selected set of parameters. Those parameters will be combinatorially expanded. The rest will remain as they were.

For a simple example, if I start with Temperature=0,100 and VDD=1.7,1.9 (a group of 4) and I select to expand based on VDD, I'll get one group with Temperature=0,100 and VDD=1.7 and a 2nd group with Temperature=0,100 and VDD=1.9.

The 2nd option is what we call a parametric set (ParamSet) expansion. For this case, each selected parameter must have the same number of values, then the corner group is expanded using the 1st value of each parameter, the 2nd value of each, and so on. Other values remained grouped as they were.

Using the same simple example, if I start with Temperature=0,100 and VDD=1.7,1.9 (a group of 4) and I select both Temperature and VDD for ParamSet expansion, I'll get one corner with Temperature=0 and VDD=1.7 and a 2nd group with Temperature=100 and VDD=1.9.

Bonus Tip: Once you've set up a lot of corners and corners groups, you can select their columns in the Corners Setup form and choose RMB->Create Corner Group. The tool will collapse the columns down, combining common variable values, into the smallest possible number of corner groups. This makes your corners setup much easier to manage.

Extra Bonus Tip: After you've gone through all this great work, you'll probably want to reuse these corner definitions for other designs. Simply use the Save icon at the top of the Corner Setup form to save them to a file. You can use the Load icon to load them in the next design, or use the cdsenv variable:

envSetVal( "adexl.gui" "defaultCorners" 'string "myDefaultCorners.sdb" )

in your .cdsinit file to have the same corners setup every time you create a new ADE XL view.

The ability to create, group and expand corners to suit different design needs makes it much easier to perform all your circuit verification and analysis.

Stacy Whiteman

Improved IDF Tool Automatically Fixes Design Rule Violations in Virtuoso

Hiro Ishikawa — Tue, 13 Dec 2011 19:00:00 GMT

Although many automatic layout generation tools are available to automate design creation, the layout modification/correction step (fixing design rule violations) is not automated very well. Consequently, design modification including error correction typically needs to be done manually. A good solution to automate the layout modification/correction step can be provided by a layout optimization tool that optimizes the areas containing design rule violations in a layout, and fixes the violations automatically. Such a capability is provided by the Interactive Design violation Fixing (IDF) tool that was first provided in the Virtuoso IC6.1.4 release.

The primary advantages of IDF are:

1. Only required areas are modified and corrected (nothing will be changed outside of the selected areas.)

2. It can be called any time in any design phase (even if the layout has not been finalized.)

3. Quality of the modified layout is stable (the results won't vary according to engineers' experience or design manner.)

As the first step to realize the above requirements, IDF was implemented in our IC6.1.4 software release by freezing (not changing) details outside of specified areas. (Fig 1)

Fig 1. IDF- IC6.1.4 (freeze outside of the area to be optimized)

Although the IDF in IC6.1.4 worked very well, freezing areas around the area to be optimized had the following two limitations:

1. It takes long time when a design is big because the entire layout data needs to be loaded on the dynamic memory.

2. When multiple areas are selected, one optimization failure ("infeasible") causes the optimization failure of all selected areas. (All areas must be optimized at the same time since optimizing a design means generating a result that satisfies all requirements simultaneously.)

Therefore, IDF needed to be enhanced so that automated layout modification/correction worked regardless of the design size, and without infeasible results interrupting the flow. In the latest release, IC6.1.5, the IDF has successfully been enhanced to realize the above requirements.The solution to the problem is applying the automated correction (IDF) only to the affected region. The areas to be optimized from a design are extracted. Then, the extracted areas are sent to the IDF engine one by one (Fig. 2)

Fig 2. IDF in IC6.1.5

IDF works very fast in most cases because the size of the data is very small. The following table compares benchmark results of IDF in IC6.1.4 and in IC6.1.5. IDF in IC6.1.5 finishes all error fixing within 1 minute.

Table 1. Runtime comparison (Frozen Donut Area vs. Area Segmenting Method)

Unit [h:m:s]

Design	Size (um x um)	# of Design Rule Errors	IDF in IC6.1.4	IDF in IC6.1.5
Stdcell MX2X1	2.61x2.61	1	3s	1s
Stdcell DLY1X4	4.06x2.61	1	2s	0.5s
Stdcell ADDFX1	7.54x2.61	2	2s	0.5s
CustomDigital 1	15 x 15	7	3min 52s	4s
Analog 2	4.5 x 6.5	8	4s	1s
Analog PLL	650 x 550	30	> 2hours ^*1)	30s ^*2)

Note:

*1) Job was terminated during constraint generation phase.
*2) 2 Infeasible results were reported.

Runtime (User time) was measured.
Test Machine:
VMWare Virtual Machine
Redhat Linux 4
RAM: 1 GB

Physical Machine:
Dell Laptop PC M65
CPU :Intel Core 2 CPU 2.16GHz
RAM : 3.25 GB
OS Windows XP SP3

Figure 3 shows the biggest design used for this benchmark test.

Fig. 3 Analog PLL design 650um X 550um（# of DRC Errors 30 -> 2 : runtime = 30sec)

This approach (loading only the specified area) allows the following benefits:

No design size limitations
Very fast
Non-stop optimization despite some infeasible results

IDF in IC6.1.5 works effectively for medium / large designs. It can also handle designs of chip-level complexity. Because each optimization task is discrete, the flow does not become interrupted by an infeasible result error. Also, the runtime is very fast, since the size of each extracted cell tends to be small.

Actually, IDF in IC6.1.5 consists of multiple small IDF fixes in IC6.1.4. Because a huge amount of design time is wasted on inefficient manual modifications, IDF in IC6.1.5 is a great solution to correct errors. IDF in IC6.1.5 is the answer to industry’s demand for automatic error correction.

Hiroshi Ishikawa

Sr. Engineering Manager, Physical Design
San Jose R&D, Custom IC, Silicon Realization Group

Cadence is the OpenText Connectivity Partner of the Year

NewYorkSteve — Mon, 28 Nov 2011 22:00:00 GMT

Cadence is pleased to be honored by the OpenText Global Partners Program as their 2011 Connectivity Partner of the Year. The award is a reflection of the close working relationship that we have had with OpenText over the past several years, providing our mutual customers with the best experiences when using Cadence Virtuoso tool suite with OpenText's ExceedOn Demand product line, which provides remote access to Virtuoso. We have done a number of webinars and joint papers to describe how best for our customers to set up both tools to maximize the benefits, particularly when working in a globalized work environment. Once again, on behalf of Cadence, I'd like to thank OpenText for their generous acknowledgment.

The following resources provide more information about OpenText and ExceedOn Demand.

Blog Post

http://www.cadence.com/Community/blogs/ii/archive/2011/07/28/q-amp-a-how-opentext-provides-remote-access-to-virtuoso.aspx

Whitepaper

http://connectivity.opentext.com/resource-centre/whitepapers/achieving-optimal-performance-with-cadence-virtuoso.aspx

Video

http://www10.edacafe.com/video/Get-free-evaluation-OpenText-Exceed-onDemand-OpenText-Remote-Connectivity-Cadence-Virtuoso-Stephen-Lewis/35159/media.html

Webinar

http://www.cadence.com/cadence/events/Pages/event.aspx?eventid=442

Steve Lewis

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

Team SKILL — Mon, 14 Nov 2011 15:00:00 GMT

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

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

A Moment to Mourn -- John McCarthy, Father of Lisp

Team SKILL — Mon, 31 Oct 2011 18:00:00 GMT

Here lies a Lisper
Uninterned from this mortal package
Yet not gc'd
While we retain pointers to his memory

[Author unknown]

Last week (October 23rd, 2011 or 24th depending on which source you read) we lost Dr. John McCarthy, one of the great contributors to the field of computer science. I'd like to send my condolences and best wishes to friends and family he left behind.

John McCarthy was the 1971 recipient of the Turing Award for his contributions to the field of artificial intelligence. But the reason we remember him and pay tribute to him today is because he is generally acknowledged as being the Father of Lisp which in some sense also makes him the grandfather of SKILL.

In 1960 McCarthy published a paper entitled Recursive Functions of Symbolic Expressions and Their Computation by Machine (Part 1). In this paper (part 2 of which was never published) he introduced a system he called LISP in which he was able to represent algorithms and mathematical logic in terms of what he called m-expressions and s-expressions. In fact, many of the names of the primitive objects and operators in the SKILL programming language were first mentioned from that paper, including: car, caar, cadar, cdr, assoc, atom, nil, null, eq, cons, lambda, quote, and list.

From the stories I've been told, McCarthy originally did not intend Lisp to become an actual language. Rather he simply illustrated it as a discussion exercise to his students. He used an M-expression notation such as F[G[a,b]] to expression function calling syntax. Some of his ambitious students were determined that they could create actual implementation on their IBM 704 mainframes based on McCarthy's theoretical concepts.

The students used an easier to parse s-expression syntax such as (F (G A B)). McCarthy hoped they'd eventually implement a better surface syntax. However, his students were initially more interested in how the language worked than the syntax. Meanwhile they also learned to love this internal (((syntax))). Eventually a student did manage to implement the m-expression syntax as originally conceived by McCarthy, but by that time none of the students wanted to use it.

Lisp is truly a great contribution to the world of computer science and software development in general.

Thanks John McCarthy. Rest in Peace.

Jim Newton

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

Team SKILL — Mon, 17 Oct 2011 13:00:00 GMT

In the previous posting Introduction to Classes -- Part 2 we saw the high level function for initializing, solving, and displaying the sudoku puzzle.

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

In this posting we'll look at the definition of the SkuSudoku class as well as the definitions of the functions SkuNew, SkuInitialize, and SkuPrint. We leave the function SkuFindSolution until next posting.

In this posting, you'll see some examples of non-trivial class and instance manipulation which completely avoid the topic of methods. Although the SKILL++ object system provides a powerful method manipulation capability, you are not required to understand anything about methods to implement applications that operate on classes.

Non-trivial slot initialization

In the previous posting we saw how to use @initform to initialize instance slots to constant/default values. But the @initform can do more than provide constant defaults. The expression provided by @initform is actually SKILL++ code which runs every time an instance is created with makeInstance. The code in this SKILL++ expression is allowed to reference any global or local function or variable, such as functions defined within an labels as shown in the example below.

The SkuSudoku class defined below represents the sudoku board itself. It has a list of 81 cells, a list of 9 columns, a list of 9 rows, and a list of 9 3x3 blocks. Notice that the class SkuSudoku is defined inside a (labels ...) which defines a local function named repeat, and that local function is referenced inside the @initform expression.

In particular, in the class definition, the three slots (rows, columns, and b3x3s) each have a different @initform expression which each reference the local function repeat.

(labels ((repeat (n unary "xU")
          ;; call the given function N number of times,
          ;; collecting the return values.
          (when (plusp n)
            (cons (unary (sub1 n))
                  (repeat (sub1 n) unary)))))
  (defclass SkuSudoku ()
     ((cells   @initform nil)
      (rows    @initform (repeat 9 (lambda (n)
                                     (makeInstance 'SkuRow    ?index n))))
      (columns @initform (repeat 9 (lambda (n) 
                                     (makeInstance 'SkuColumn ?index n))))
      (b3x3s   @initform (repeat 9 (lambda (n) 
                                     (makeInstance 'SkuB3x3   ?index n)))))))

A call to the SKILL primitive makeInstance such as an evaluation of the expression (makeInstance 'SkuSudoku) will create an instance of the class and will initialize the 4 slots by evaluating the 4 respective @initform expressions. Furthermore, the expressions will be evaluated such that the local function repeat is defined.

Encapsulation through lexical scoping

Note that the feature of encapsulation (the ability to limit the visibility of functions like repeat) is provided by SKILL++ lexical scoping. This is different from the C++/Java paradigm which forces you to use the object system to implement encapsulation. In SKILL++, encapsulation works with or without the object system, so all SKILL++ programs can take advantage of it, not just object-oriented programs.

Initialization using a factory function

There is a limit to how much initialization is possible from the @initform expressions. In particular the @initform expressions are not allowed to reference each other. Furthermore, you have no guarantee in which order the initialization expressions will evaluate. This lack of guarantee is especially important when define classes using single inheritance, and even more important in the case of multiple inheritance. All @initform expressions need to be mutually independent expressions which only depend on the environment of the defclass and not on each other.

Skill++ programs typically create instances of classes in one of two ways: either by a direct call to makeInstance or by a call to an intermediate function which calls makeInstance. Such an intermediate function is called a factory function. A benefit of a factory function is that the function may also preform any additional initialization as necessary for the correct behavior of the program.

There is still another advantage to using a factory function rather than a direct call to makeInstance. The function can initialize slots so that their initial values depend on each other. In the case of a properly initialized sudoku board, the cells, rows, columns, and 3x3 blocks all depend on each other in a particular way. There is a list of 81 cells cells slot, and each of these cell objects is in the correct row, column, and 3x3 block. The sudoku board cannot be initialized simply by the @initform expressions. The job of SkuNew is to assure that the cells, rows, columns, and 3x3 blocks reference each other properly.

A factory function typically does the following:

Allocates an instance
Initializes the slots of the instance, potentially according to the arguments of the factory function itself
Returns the initialized instance.

Creating a structurally correct sudoku board

We want to define such a factory function named SkuNew which allocates, initializes, and returns an instance of the SkuSudoku class.

The function, SkuNew, does the actual allocation via a call to makeInstance as well as setting up the structure of the board independent of the actual content of the particular sudoku solution. In particular SkuNew assures that each cell can easily access its row, column, and 3x3 block and that each row, column, and 3x3 block can easily access its cells.

(defun SkuNew ()
  ;; allocate a blank-slate instance of SkuSudoku representing an empty
  ;; sudoku board
  (let ((sudoku (makeInstance 'SkuSudoku)))
    (let ((index 0))
      (foreach row sudoku->rows
        (foreach col sudoku->columns
          (let ((cell (makeInstance 'SkuCell ?index index++))
                (b3x3 (nth (xplus (xtimes 3
                                        (xquotient row->index 3))
                                 (xquotient col->index 3))
                            sudoku->b3x3s)))
             ;; add the cell to the list of sudoku cells.
             sudoku->cells = (cons cell sudoku->cells)
 
             ;; tell the cell which row, column
             ;; and 3x3 block it belongs to.
             cell->row    = row
             cell->column = col
             cell->b3x3   = b3x3
             
             ;; tell the row, col, and 3x3 block
             ;; that this cell belongs to it.
             row->cells  = (cons cell row->cells)
             col->cells  = (cons cell col->cells)
             b3x3->cells = (cons cell b3x3->cells)))
    ;; return the new instance.
    sudoku))

Feeding in the partial solution

Finally, given an initialized and consistent object which represents the sudoku board, it is necessary to feed in a given partial solution in preparation for running the solution algorithm, SkuFindSolution. The function SkuInitialize iterates through the rows and columns of a given SkuSudoku instance, filling some of the cells with a number from 0 to 9 as per the given partial solution.

(defun SkuInitialize (sudoku partial_solution)
  ;; feed in the partial solution
  (foreach (sudoku_row solution_row) sudoku->rows partial_solution
    (foreach (cell solution) sudoku_row->cells solution_row
      (when (numberp solution)
        cell->value = solution)))
  sudoku)

The sudoku instance initialization protocol

The two functions together form the sudoku initialization protocol:

SkuNew Create a newly allocated, structurally correct sudoku board, complete with cross-references which allow for effeciently search. SkuInitialize Feed a given partial solution into a given structurally correct sudoku board. Now you may experiment with the functions, SkuInitialize, and SkuNew by evaluating an expression such as the following in the CIWindow.

(SkuInitialize (SkuNew)
               '((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)))

==>
stdobj@0x1d454234

The printed object such as stdobj@0x1d454234 is how an instance of a SKILL++ class is printed.

Displaying an instance

The default way an instance of a SKILL++ class prints is not very informative. We need to write a special purpose function, SkuPrint to display the partial (or full) state of the sudoku board.

The following function SkuPrint generates a string representing the ASCII representation of the sudoku board. The string contains \n characters so you'll have to use (printf "%s" ...) or a similar function to print it so it is human readable.

(defun SkuPrint (sudoku)
  (let ((divider "+-----------------+\n"))
    (strcat divider
            (buildString (foreach mapcar row sudoku->rows
                           (strcat "|"
                                   (buildString (foreach mapcar cell row->cells
                                                  (if cell->value
                                                      (sprintf nil "%d" cell->value)
                                                      " "))
                                                ;; separate the cells with |
                                                "|")
                                   "|"))
                         ;; separate the lines with \n
                         "\n")
            "\n"
            divider)))

You may now print the object with a call to printf as follows.

(printf "%s\n"
        (SkuPrint (SkuInitialize (SkuNew)
                                 '((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)))))
==>
+-----+-----+-----+
|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|
+-----+-----+-----+

Enhancements in IC615

The approach and the actual code shown here works in versions of SKILL++ using IC5033, IC5141, and IC61 up to and including IC615. However, there are some new features in IC615 which make initialization and presentation of SKILL++ objects easier and more flexible. To completely understand these and other new features, you'll need to understand something about generic functions and methods, which SKILL for the Skilled has not addressed yet, but here is a little taste.

There is a new generic function defined called printself. Virtuoso calls printself on SKILL++ instances when printing them into the CIWindow, stacktraces, or as a result of (printf ... "%L"). You may provide a method of printself specializing on your class which provides a string for the SKILL++ implementation to use as the printed representation of your object.
In IC615 makeInstance calls the generic function initializeInstance on a SKILL++ instance before returning it. You are allowed to provide what is called an @after method on initializeInstance specializing on your SKILL++ class to initialize it. This means that any application which makes an instance of your class will automatically call your initialization code without having to know the name of your factory function.
In IC615 defclass allows you to define classes which inherit from multiple potentially independent or interrelated superclasses called mix-in classes. In this case the various methods on initializeInstance are even more important as each such method is able to initialize the slots of an instance it is responsible for.

Review

In this posting you have seen some examples of non-trivial SKILL++ class allocation and initialization using both @initform and by a factory function. You've also seen a way to present SKILL++ objects in human readable form depending on the semantics of your particular class.

Preview

In the next posting of SKILL for the Skilled we'll finally look at how to implement the function SkuFindSolution which is the last function needed to complete the implementation of SkuSolve function.

Jim Newton