A Sudoku Solver in C 1.11

A Sudoku Solver in C is a console-based Linux program, written in C language, that solves Su Doku puzzles using deductive logic

Developer:   Bill DuPree       more software by author → Price:  0.00 License:   GPL (GNU General Public License) File size:   27K Language:    OS:    Rating:   0 /5 (0 votes) Your vote:   enlarge screenshot

A Sudoku Solver in C is a console-based Linux program, written in C language, that solves Su Doku puzzles using deductive logic. It will only resort to trial-and-error and backtracking approaches upon exhausting its deductive moves.

Puzzles must be of the standard 9x9 variety using the (ASCII) characters 1 through 9 for the puzzle symbols. Puzzles should be submitted as 81 character strings which, when read left-to-right will fill a 9x9 Sudoku grid from left-to-right and top-to-bottom. In the puzzle specification, the characters 1 - 9 represent the puzzle givens or clues. Any other non-blank character represents an unsolved cell.

The puzzle solving algorithm is home grown. I did not borrow any of the usual techniques from the literature, e.g. Donald Knuth's "Dancing Links." Instead I rolled my own from scratch as a personal challenge. As such, its performance can only be blamed on yours truly. Still, I feel it is quite fast. On a 333 MHz Pentium II Linux box it solves typical medium force puzzles in approximately 800 microseconds or about 1,200 puzzles per second, give or take. On an Athlon XP 3000 it solves about 6,600 puzzles per sec. (Solving time is dependent upon degree of difficulty, so YMMV.)

Description of Algorithm:

The puzzle algorithm initially assumes every unsolved cell can assume every possible value. It then uses the placement of the givens to refine the choices available to each cell. I call this the markup phase.

After markup completes, the algorithm then looks for singleton cells with values that, due to constraints imposed by the row, column, or 3x3 region, may only assume one possible value. Once these cells are assigned values, the algorithm returns to the markup phase to apply these changes to the remaining candidate solutions. The markup/singleton phases alternate until either no more changes occur, or the puzzle is solved. I call the markup/singleton elimination loop the Simple Solver because in a large percentage of cases it solves the puzzle.
If the simple solver portion of the algorithm doesn't produce a solution, then more advanced deductive rules are applied.

I've implemented two additional rules as part of the deductive puzzle solver. The first is subset elimination wherein a row/column/region is scanned for X number of cells with X number of matching candidate solutions. If such subsets (or tuples) are found in the row, column, or region, then the candidates values from the subset may be eliminated from all other unsolved cells within the row, column, or region, respectively.

The next deductive rule examines each region looking for candidate values that exclusively align themselves along a single row or column, i.e. a vector. If such candidate values are found, then they may be eliminated from the cells outside of the region that are part of the aligned row or column.

Note that each of the advanced deductive rules calls all preceeding rules, in order, if that advanced rule has effected a change in puzzle markup.

Finally, if no solution is found after iteratively applying all deductive rules, then we begin trial-and-error using recursion for backtracking. A working copy is created from our puzzle, and using this copy the first cell with the smallest number of candidate solutions is chosen. One of the solutions values is assigned to that cell, and the solver algorithm is called using this working copy as its starting point. Eventually, either a solution, or an impasse is reached.

If we reach an impasse, the recursion unwinds and the next trial solution is attempted. If a solution is found (at any point) the values for the solution are added to a list. Again, so long as we are examining all possibilities, the recursion unwinds so that the next trial may be attempted. It is in this manner that we enumerate puzzles with multiple solutions.

Note that it is certainly possible to add to the list of applied deductive rules. The techniques known as "X-Wing" and "Swordfish" come to mind. On the other hand, adding these additional rules will, in all likelihood, slow the solver down by adding to the computational burden while producing very few results. I've seen the law of diminishing returns even in some of the existing rules, e.g. in subset elimination I only look at two and three valued subsets because taking it any further than that degraded performance.

What's New in This Release:

Code optimization has resulted in a 30% increase in speed.
tags the puzzle  row column  deductive rules  the markup  the row  the next  candidate solutions  the algorithm  from the  eliminated from  recursion unwinds  are found  next trial  

Download A Sudoku Solver in C 1.11

 http://www.techfinesse.com/game/solver.tar.gz
 http://www.techfinesse.com/game/solver.tar.bz2

Authors software

A Sudoku Solver in C 1.11 (by Bill DuPree) A Sudoku Solver in C is a console-based Linux program, written in C language, that solves Su Doku puzzles using deductive logic

sshutout 1.0.3 (by Bill DuPree) sshutout is a daemon that periodically monitors log files, looking for multiple failed login attempts via the Secure Shell daemon.

Similar software

A Sudoku Solver in C 1.11 (by Bill DuPree) A Sudoku Solver in C is a console-based Linux program, written in C language, that solves Su Doku puzzles using deductive logic

Sudoku Savant 1.1 (by Chris Rankin) Sudoku Savant is a simple GUI-driven application to solve and generate Sudoku puzzles through logical means. Sudoku Savant genera

Su-per-Doku 2.1 (by Matt Sarah) Su-per-Doku is a sudoku puzzle game dekstop widget for SuperKaramba

Zudoku 1.0 (by Figlabs Ltd) Zudoku is a free Sudoku game for all platforms. Sudoku, sometimes written Su Doku, is a logic-based placement puzzle, also known as

sudoku 1.6.0 (by Victor Alamo) sudoku is a very simple sudoku game. Sudoku, sometimes spelled Su Doku, is a logic-based placement puzzle, also known as Number Pl

ksudoku 0.3 (by Francesco Rossi) KSudoku is a program that can generate and solve sudoku (en.wikipedia.org/wiki/Sudoku) puzzles (of different difficulty level) using

Python Sudoku 0.12.4 (by Xose Otero) Python Sudoku is a text and graphical program (gtk interface) to create or resolve sudokus

Sudokut 0.3 (by Bernard Desgraupes) Sudokut is a command line solver for Sudoku puzzles

FLTK Sudoku 2005-12-09 (by Michael R Sweet) FLTK Sudoku is an implementation of the popular Sudoku game (sometimes called Number Place) based on the Fast Light Toolkit

Kagiru 0.25 (by Roel Hertoghs)

Other software in this category

GCompris 8.2.2 (by bruno) GCompris is an educational software which propose different activities to kids from 2 to 10

S.C.O.U.R.G.E. 0.16 (by Gabor Torok) S.C.O.U.R.G.E

OCC 1.2.6 (by kulkanie) Online Chess Club (OCC) is a small PHP chess game. Note: If you don't know what PHP is don't bother to download

tower toppler 1.1.2 (by Andreas R?ver) In tower toppler you have to help a cute little green animal switch off some kind of "evil" mechanism

Triptych 1.17 (by Chronic Logic LLC) Triptych is a fast-paced physics based block dropping game that will keep you coming back for more