## Sudoku## Outline- Rules of Sudoku
- Link to Fisher
- Solving Sudoku manually
- Knuth's computational method
- Number of valid boards
## Rules9x9 grid made up of 3x3 subgrids (called ' Some cells already contain numbers, known as ' 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 ## HistoryInvented 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 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 FisherSudoku solutions are a subset of
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
## Scanning1. If there is only one candidate for that cell - enter that number into it.
2. If there is only one possible location for a number in a row, column or block - enter it.
## Marking UpThe 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 However, some 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 SolutionYou 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, 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? - There is
**a**number in that square. - There is a 7 in row 2.
- There is a 7 in column 3.
- There is a 7 in block 6.
So placing a number satisfies 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 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 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 gridsBack 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 = 9 Number of valid grids without the column/row rules: B = 9! Number of valid grids without the column rule: C = [9!*(2+6*3*3)*3! (I spell out where that figure comes from here)
Number of valid grids: 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. |