[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / sudoku.rjb
Tue Sep 18 15:27:13 PDT 2007

# Sudoku Solving with a Computer

## Sizes

I use smaller grids to try out ideas.

SizeRegion|Regions|Digits
4><42><241,2,3,4
6><63><26 (2><3 layout)1,2,3,4,5,6
9><93><391,2,3,4,5,6,7,8,9
16><164><4160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

The elegance and intrigue of the puzzle comes from

1. the number of rows in the big grid is equal to the number of columns
and equal to the number of squares in each region.

## Sudoku by Hand

• I solve tough 9><9s in 2 or 3 days of spare time.
• A gentle 9><9, on a Palmtop takes about an hour.
• But I'm still learning.
• Just about every trick I use can be found at [ Sudoku#Solution_methods ] on the Wikipedia:
1. Marking up
2. Cross Hatching
3. Counting -- what is missing
4. Contingencies
5. Analysis -- Digit Patterns
6. Analysis -- What-if

1. I've found a spreadsheet helps.
It helps with book keeping.
• Recording deduced digits
• Marking up Possible digits
• What-if: copy and work each in turn.
• Automatic Marking of Possibilities
Demo: 4><4

## Permutations: A step to a simple program

Each row, column and region has the same digits in various orders.

These are called permutations.

The ideal program would read something like:

1. Define a board,
2. perm(row1, digits),
3. perm(row2, digits),
4. ...

where
2. perm(List, Digits)::=List is a permutation of Digits.

Ideally the perm statement would either test a known list, or fill in blanks in a list, and it should, if necessary try other permutations in turn until they fit.

Prolog makes this trivial.

## Prolog

Prolog is a useful prototyping tool.

I like to have fashionable examples in my CSci320 class.

I developed one from the first Harry Potter book.

You can express the problem in Prolog language and it will search for a solution.

## Sudoku Simply Solved

As I expected this work well with small (4><4) examples [ ../cs320/prolog/sudoku4.plg ]

Demo.

I knew it would need optimization to tackle a 9><9 problem.

Key optimizations

1. Unrolling logic in special cases: No loops!
2. A neat way to check if a list of digits has each digit precisely once.
3. Rejecting permutations as soon as possible.
1. When first three rows generated can test first row of regions.
2. Keep track of what is placed in the columns and don't repeat.

No longer simple: [ ../cs320/prolog/sudoku9.plg ]

It still takes hours to run.

## Sudoku Slowly Solved

The reason is simple.
1. The programs work by generating every possible permutation in turn.
2. With N rows/digits/regions there are 1*2*3*4* ... *N permutations of one row.
3. Short hand N! = 1*2*3*4* ... *N.
4. But we have N rows.
So the number of cases tried is (N!)^N

NN!(N!)^NApproximatelyTimes
1111
2244*10^0
362162*10^2
424331,7763*10^5<0.1 second
512024,883,200,0002*10^11
6720...10^17
75,040...10^26
840,320...10^37
9362,880...10^503..4 hours
......
(Thanks to Allen King for the use of the Apple Mac Scientific calculator).

## Artificial Stupidity vs Artificial Intelligence

Standard computer science predicts that the time will be dominated by the above numbers.

Often simple solutions are not feasible.

Next:
(Fast solutions to sudoku): Dr. Kerstin Voigt's work: [ seminar.html ]

(sudoku seminar plan): [ sudoku.html ]

(Wikipedia): A social encyclopedia [ http://www.wikipedia.org/ ]

(Notes on the mathematics of Sudoku): demonstration of MATHS [ ../maths/ ] in action [ sudoku.maths.html ]

## Abbreviations

3. TBD::="To be Done".

## Acknowledgment

The support of the National Science Foundation under award 9810708 is gratefully acknowledged.

. . . . . . . . . ( end of section Sudoku Solving with a Computer) <<Contents | End>>