Sudoku

 

Outline

  1. Rules of Sudoku
  2. Link to Fisher
  3. Solving Sudoku manually
  4. Knuth's computational method
  5. Number of valid boards

Rules

9x9 grid made up of 3x3 subgrids (called 'blocks').

Some cells already contain numbers, known as 'givens'.

Goal: fill in the empty cells, one number in each, so that each column, row, and block contains the numbers 1 through 9 exactly once.

Simple rules, but NP-complete

History

Invented US 1970 by Dell publishers

Became popular in Japan

Literally Doku=Single Su=Number

Wayne Gould developed a computer program that spontaneously produces puzzles (took over six years).

He promoted the puzzle to The Times in Britain, which launched it on 12 November 2004.

3 days later the Daily Mail followed suit and shortly thereafter the other Nationals jumped on the band wagon.

Now spread to circa 25 countries.

Sudoku, Latin Squares, and Fisher

Sudoku solutions are a subset of 'Latin Squares' invented by Euler

Fisher recommended: in order to randomize trials on crops say you should distribute your crop according to a random Latin square.

He tabulated all Latin squares up to n=6.

Here's one in use for Spruce tree trials (second most interesting thing in Bedgelert):

 

Quentin and I know all this of course as Fisher was at Caius and has a stained glass window in the hall there.

 

Manual Solution

Candidates = possible values a cell can take

Marking up = using the givens plus the puzzle rules to eliminate candidates

Scanning = entering in values

Scanning

1. If there is only one candidate for that cell - enter that number into it.

     
     
     
     
     
     
     
1    
7    
     
     
  8 3
     
     
     
2 9  
    4
?    
     
     
     
     
     
     
5    
     
     

2. If there is only one possible location for a number in a row, column or block - enter it.

     
     
     
     
2    
     
     
     
     
     
     
     
  6  
  ?  
  8  
     
     
     
     
     
     
     
     
    2
     
     
     

Marking Up

The simplest rules are to eliminate any 'givens' in the row, column or block of the square of interest from the list of candidates.

In fact these 3 rules then solve most Sudoku puzzles! So most are really not that interesting, although there are a lot of constraints so spotting the moves quickly is the human challenge.

However, some fiendishly difficult puzzles (eg. 1,2) require more sophisticated reasoning, such as:

X-Wing and Swordfish - candidate elimination when 4/6 cells are correlated.

Nisho - make a guess for the square with the least number of candidates, follow through until a contradiction or the solution presents itself.

For more strategy tips click here

Computational Solution

You can apply the logic steps outlined above to solve Sudoku problems - and to grade their difficulty for prospective human solvers, this may be the best method.

However, Donald Knuth has a neater method. First he reformulates the problem:

Given a blank grid there are 9 possible choices for each of the 81 squares.

That's 729 possible settings out of which only some subsets (of 81) form valid solutions.

Imagine putting a 7 in square (2,3) what constraints are fulfilled?

  1. There is a number in that square.
  2. There is a 7 in row 2.
  3. There is a 7 in column 3.
  4. There is a 7 in block 6.

So placing a number satisfies 4 constraints out of the total of 4x81 (one number in each square, and the numbers 1-9 in each row, column and block).

Knuth's tactic is to represent all the possible choices for each of the squares and each of the 4 constraints that each choice fulfills using a Boolean matrix:

 

The task now is to find a subset of the rows which have precisely one entry in every column.

Some rows are fixed in the subset by the 'givens'.

Knuth has already written a paper on these exact cover problems.

He shows efficient searchs can be made by recursively searching over the constraints wich are nearest to being fulfilled (ie. over the columns with the most numbers of 1s)

The formulation is nice as it treats all the constrains symmetrically (unlike a rule based approach where subsquare constraints can appear as different) and 'guesses' and 'logic' are placed on an equal footing

Given a speedy solver it's now easy to build Sudokus via brute force. (add a new element, see if it is soluble, add a new element, etc.)

Number of Sudoku grids

Back of the envelope calculation: Add in the rules seqentially and see how the number of combinations reduces.

Number of valid grids without the block/column/row rules: A = 981 (1.96 x 1077)

Number of valid grids without the column/row rules: B = 9!9 (1.09 x 1050)

Number of valid grids without the column rule: C = [9!*(2+6*3*3)*3!6]3 (8.52 x 1035)

(I spell out where that figure comes from here)

Assume: addition of column rule reduces the number of viable grids by the same fraction, R = C/B = 7.811 x 10-15

Number of valid grids: D ~ R2B = 6.6571 x 10 21

True figure: 6,670,903,752,021,072,936,960 (so enthusiasts need not worry about them drying up)

Found via a brute force search (as for Latin squares, no combinatoric solution possible)

Make the search tractable by noting symmetries: permutations of the numbers, reflections, rotations, permuting columns/rows within blocks etc.