last updated: 24 March 2007

sudoku solver

Description (from sudoku.c)

This C code solves 9x9 sudoku puzzles using "logic" not "brute force". Considering how small a problem sudoku puzzles are with modern computer speeds and memory, "brute force" is a very suitable approach even if it does lack a degree of elegance. After finishing this code, a google search of of "+sudoku +solver" revealed a link to a 3 line perl solver (actually, 20 lines formatted). Yes, that did use brute force... but doing so in 3 lines of code is remarkably elegant.

Solution Method

  1. Build 9x9 array of values and masks for possible values.
    The mask is done in powers of 2 to do logical compares (and, or, xor) instead of numeric compares. For example, a value of N=5 is 2**(N-1).
  2. Use "basic" (level-1) solver to see if a row|column|box entry only has one possible solution.
  3. Use a level-N (2 to 6) masker which checks whether row|column|box entries can be masked.
    For example, at level-3 if entries of 58,568,58 exist you know the middle entry (568) must be '6' for the first and third entries to have a solution (must be '5' or must be '8').
  4. Loop incrementing level and reverting to basic until no progress made (no unique solution available) or until solved.
    The masker should work beyond 6 levels, but I suspect it is not possible to write a non-unique puzzle which would need a higher masking level (I have yet to see a unique puzzle which needs more than 4).
  5. If no solution found (multiple solutions possible), continue executing a brute completion to show two possible solutions (may be more). Note, it is possible (-example 12) for "logic" to not find a solution and "brute" only finding one possible solution. Example 12 is a rather pathological puzzle as the solution cannot be determined without a "try this" (brute) on a cell.

Methods Considered

  1. Selected method:
    Write a program to employ logic I used solving puzzles by pencil.
  2. Brute force:
    After some basic logic guess and retry until success. Note, unless all possible solutions are tried this will likely stop with first match on a non-unique puzzle.
  3. Build all possible solutions then mask.
    This would solve a puzzle very quickly, but only after generating or re-reading the *many* possible solved puzzles. This method would be useful for detecting all possible solutions to non-unique puzzles. This method could also be useful in generating puzzles for others to solve.

Why?

When I was young, back in the day when I could multiply multi-digit numbers, add columns, or divide in my head, I would have been able to train my mind to solve most sudoku with almost no pencil work. Not so any more: too much clutter in my head and too many brain cells out-to-lunch or in semi-retirement (or just plain dead). Doing puzzles by pencil is good mental exercise and I may continue to do them to exercise those brain cells which are still responding, but I soon realized there are other (not really "better") ways. Besides, opportunity to write code, even for computer professionals, is rather rare and in the writing is a bit of artistry. Geeks do these things because they must (like other artists). Opportunity presented itself when I went on two week sick leave.

Time to Write

First hand Sudoku done 01/2006 (introduced to me by my wife). Did probably 30ish puzzles (mostly from newspaper, some from Will Shortz book). Initially, took 30-60 minutes to solve a newspaper puzzle and I would not attempt anything beyond 3 stars. By time program started (2006-01-31), had done both 4 and 5 star puzzles by hand (30-60 minutes each, down to 10ish minutes for 1 or 2 star). 

01/31 2hr  Design on paper (in outpatient waiting room)
      2hr  Initial write (initialization and structure)
02/01 2hr  Basic solver written
02/02 2hr  Level2 solver written
      2hr  Debugging and initial fluff added 
02/03 2hr  Level3 solver written, most examples solvable
02/04 4hr  Rewrite Level2|3 as generic Masker after found
           an example requiring a Level4 solver.
02/05 3hr  Additional testing/debugging/fluff and code restructures
02/06 3hr  Code cleanup and documentation writtten
02/07 3hr  Brute force solver for non-unique puzzles
02/08 3hr  Add to uak kit (man page and html, timing examples)
02/09 1hr  Pretty-up the format for initial/resolved
     ----- Time to design, write, test, re-write, document
     29hrs
This might make a good programming course problem. Young minds should be able to write this quicker, provided they can comfortably/fluently write C. Note, a functional solver was available in 12 hours. Some fluff already included by then and more added.

Writen on Mac OSX, code should work "as is" on Linux or any UNIX variant. Tested on Irix and AIX.

Notes

For the 3 line perl brute force solver see Edmund von der Burg's blog: 

http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html
The "brute forces" is a bit slower to execute than using logic, but it works.
Some timing comparisons (in minutes:seconds) for the 9 coded examples: 
        sudoku.c, logic      perl, brute  | sudoku.c, logic      perl, brute
        Elapsed   CPU    Elapsed   CPU    | Elapsed   CPU    Elapsed   CPU 
Example -------   ---    -------   ---    | -------   ---    -------   ---
  #1:      0.02    0.00     2.63     2.60 |    0.01    0.00     2.04    1.76
  #2:      0.01    0.00    18.49    18.44 |    0.01    0.00    13.31   12.20
  #3:      0.01    0.00  3:29.02  3:28.98 |    0.01    0.00  2:30.29 2:20.03
  #4:      0.01    0.00     3.29     3.26 |    0.01    0.01     2.45    2.20
  #5:      0.01    0.00  1:50.63  1:50.58 |    0.01    0.00  1:19.72 1:12.93
  #6:      0.00    0.00    10.12    10.06 |    0.01    0.00     7.02    6.47
  #7:      0.00    0.00    22.24    22.16 |    0.01    0.00    15.38   14.20
  #8:      0.02    0.01     0.63     0.59 |    0.02    0.02     0.50    0.39
  #9:      0.01    0.00     0.14     0.10 |    0.01    0.00     0.09    0.07
                                          |
System: IBM p650 1.1ghz running AIX 5.2   | MacOSX 10.4.3 PowerPC G4 1.5ghz
As expected, for a non-unique puzzle the brute-force sudoku.perl script stops on the first match (example #8) while sudoku.c generates two possible solutions. Both successfully detect an invalid puzzle (example #9), sudoku.prl exits quietly while sudoku.c reports when it found the problem.

Example

iceberg2: sudoku -example 3

_Pocket Sudoku_ Volume 3, #145   (Will Shortz)
Level -1 Known 22, Unknown 59, Solved 0, Errors 0
+---------------+---------------+---------------+
| (2)  (1)   .  |  .    .    .  |  .    .    .  |
|  .    .    .  |  .    .   (3) | (1)   .    .  |
|  .    .   (9) | (4)   .    .  |  .    .   (7) |
+---------------+---------------+---------------+
| (8)  (2)  (5) |  .    .   (4) |  .    .    .  |
|  .    .    .  | (6)   .    .  |  .    .    .  |
| (1)   .    .  |  .    .   (8) | (2)   .    .  |
+---------------+---------------+---------------+
|  .   (7)   .  |  .   (9)   .  |  .    .    .  |
|  .    .    .  |  .   (3)  (1) |  .   (4)   .  |
|  .    .    .  |  .    .    .  | (3)  (8)   .  |
+---------------+---------------+---------------+

_Pocket Sudoku_ Volume 3, #145   (Will Shortz)
Level  3 Known 22, Unknown 0, Solved 59, Errors 0
+---------------+---------------+---------------+
| (2)  (1)   8  |  9    6    7  |  4    3    5  |
|  5    4    7  |  2    8   (3) | (1)   9    6  |
|  3    6   (9) | (4)   1    5  |  8    2   (7) |
+---------------+---------------+---------------+
| (8)  (2)  (5) |  1    7   (4) |  9    6    3  |
|  7    3    4  | (6)   2    9  |  5    1    8  |
| (1)   9    6  |  3    5   (8) | (2)   7    4  |
+---------------+---------------+---------------+
|  4   (7)   3  |  8   (9)   2  |  6    5    1  |
|  6    8    2  |  5   (3)  (1) |  7   (4)   9  |
|  9    5    1  |  7    4    6  | (3)  (8)   2  |
+---------------+---------------+---------------+

iceberg2: sudoku -help
sudoku  # sudoku v2.1
  -h    this usage information
  -e N  where N is one of 17 internal examples
  -f    list of internal examples
  -b B  where B is number unique solutions when brute invoked
        (defaults as 2)
  -l L  where L is level to start solving (1 to 8)
  -m M  where M is maximum level to mask, maximum 8
  -s S  show level (bit mask), default 0, where:
     0  initial/results only
     1  possible values
     2  eliminated values
     4  octal mask (possible)
  -i    show initial only
  -p    show progress to solution
  -q    quiet option
  -v    verbose option
  -z    output progress in perl brute format

The puzzle is read from stdin in 9 rows of 9 numbers,
unless '-example N' is specfied for a pre-built example.
Use 0 (or any of: '.*x') for a missing value.
Use a space, any other punctuation, or nothing delimit values.
End of Story