[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / sudoku.rjb
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Tue Sep 18 15:27:13 PDT 2007

Contents


    Sudoku Solving with a Computer

      Author -- Richard J Botting

      Sizes

      I use smaller grids to try out ideas.

      A 4><4 grid of boxes with 5 numbers filed in.

      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

      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

      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 ]

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

End