Cadence® system design and verification solutions, integrated under our Verification Suite, provide the simulation, acceleration, emulation, and management capabilities.
Verification Suite Related Products A-Z
Cadence® digital design and signoff solutions provide a fast path to design closure and better predictability, helping you meet your power, performance, and area (PPA) targets.
Full-Flow Digital Solution Related Products A-Z
Cadence® custom, analog, and RF design solutions can help you save time by automating many routine tasks, from block-level and mixed-signal simulation to routing and library characterization.
Overview Related Products A-Z
Driving efficiency and accuracy in advanced packaging, system planning, and multi-fabric interoperability, Cadence® package implementation products deliver the automation and accuracy.
Cadence® PCB design solutions enable shorter, more predictable design cycles with greater integration of component design and system-level simulation for a constraint-driven flow.
An open IP platform for you to customize your app-driven SoC design.
Comprehensive solutions and methodologies.
Helping you meet your broader business goals.
A global customer support infrastructure with around-the-clock help.
More Support Log In
24/7 Support - Cadence Online Support
Locate the latest software updates, service request, technical documentation, solutions and more in your personalized environment.
Cadence offers various software services for download. This page describes our offerings, including the Allegro FREE Physical Viewer.
The Cadence Academic Network helps build strong relationships between academia and industry, and promotes the proliferation of leading-edge technologies and methodologies at universities renowned for their engineering and design excellence.
Participate in CDNLive
A huge knowledge exchange platform for academia to network with industry. We are looking for academic speakers to talk about their research to the industry attendees at the Academic Track at CDNLive EMEA and Silicon Valley.
Come & Meet Us @ Events
A huge knowledge exchange platform for academia. We are looking for academic speakers to talk about their research to industry attendees.
Americas University Software Program
Join the 250+ qualified Americas member universities who have already incorporated Cadence EDA software into their classrooms and academic research projects.
EMEA University Software Program
In EMEA, Cadence works with EUROPRACTICE to ensure cost-effective availability of our extensive electronic design automation (EDA) tools for non-commercial activities.
Apply Now For Jobs
If you are a recent college graduate or a student looking for internship. Visit our exclusive job search page for interns and recent college graduate jobs.
Cadence is a Great Place to do great work
Learn more about our internship program and visit our careers page to do meaningful work and make a great impact.
Get the most out of your investment in Cadence technologies through a wide range of training offerings.
Overview All Courses Asia Pacific EMEANorth America
Instructor-led training [ILT] are live classes that are offered in our state-of-the-art classrooms at our worldwide training centers, at your site, or as a Virtual classroom.
Online Training is delivered over the web to let you proceed at your own pace, anytime and anywhere.
Exchange ideas, news, technical information, and best practices.
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.
It's not all about the technology. Here we exchange ideas on the Cadence Academic Network and other subjects of general interest.
Cadence is a leading provider of system design tools, software, IP, and services.
Get email delivery of the Cadence blog featured here
Just for a reminder, here is the definition of the top level
(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
SkuFindSolution, the function which actually searches for
the sudoku solution.
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
(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))))
Now you can test the program by copying the following into the CIWindow which
comes from the Sudoku
(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
(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|+-----------------+
The SkuSolve function is good at detecting that no
solution exists for a particular puzzle.
(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
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:
The particular implementation of SkuFindSolution also
shows an example of how to use SKILL++ local functions. This usage
avoids polluting the global function space.
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.