Number of valid grids: D ~ R 2 B = 6.6571 x 10 21 (I spell out where that figure comes from here)Īssume: 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 without the column rule: C = 3 (8.52 x 10 35) Number of valid grids without the column/row rules: B = 9! 9 (1.09 x 10 50) Number of valid grids without the block/column/row rules: A = 9 81 (1.96 x 10 77) (add a new element, see if it is soluble, add a new element, etc.)īack of the envelope calculation: Add in the rules seqentially and see how the number of combinations reduces.

Given a speedy solver it's now easy to build Sudokus via brute force. 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 over the columns with the most numbers of 1s) He shows efficient searchs can be made by recursively searching over the constraints wich are nearest to being fulfilled (ie. Knuth has already written a paper on these exact cover problems. Some rows are fixed in the subset by the 'givens'. The task now is to find a subset of the rows which have precisely one entry in every column. 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: 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). Imagine putting a 7 in square (2,3) what constraints are fulfilled? That's 729 possible settings out of which only some subsets (of 81) form valid solutions. Given a blank grid there are 9 possible choices for each of the 81 squares. However, Donald Knuth has a neater method. 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. Nisho - make a guess for the square with the least number of candidates, follow through until a contradiction or the solution presents itself. X-Wing and Swordfish - candidate elimination when 4/6 cells are correlated. 1, 2) require more sophisticated reasoning, such as: However, some fiendishly difficult puzzles (eg. 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. The simplest rules are to eliminate any 'givens' in the row, column or block of the square of interest from the list of candidates. Here's one in use for Spruce tree trials (second most interesting thing in Bedgelert): He tabulated all Latin squares up to n=6. Sudoku solutions are a subset of 'Latin Squares' invented by Eulerįisher recommended: in order to randomize trials on crops say you should distribute your crop according to a random Latin square. He promoted the puzzle to The Times in Britain, which launched it on 12 November 2004.ģ days later the Daily Mail followed suit and shortly thereafter the other Nationals jumped on the band wagon. Wayne Gould developed a computer program that spontaneously produces puzzles (took over six years). 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. Some cells already contain numbers, known as ' givens'. 9x9 grid made up of 3x3 subgrids (called ' blocks').

Np complete sudoku rules