Sudoku Solving with a Computer

Author -- Richard J Botting

Sizes

I use smaller grids to try out ideas.



Size	Region	|Regions|	Digits
4><4	2><2	4	1,2,3,4
6><6	3><2	6 (2><3 layout)	1,2,3,4,5,6
9><9	3><3	9	1,2,3,4,5,6,7,8,9
16><16	4><4	16	0,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
  
  

Spreadsheets as an aid

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
   
   

   N	N!	(N!)^N	Approximately	Times
   1	1	1	1
   2	2	4	4*10^0
   3	6	216	2*10^2
   4	24	331,776	3*10^5	<0.1 second
   5	120	24,883,200,000	2*10^11
   6	720	...	10^17
   7	5,040	...	10^26
   8	40,320	...	10^37
   9	362,880	...	10^50	3..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 ]

   Links

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