Sudoku Puzzle Theory

Sudoku is all about permutations, but permutations with an extra twist of logic. To look into the theory behind Sudoku you need to first look into permutations.

Permutations

A permutation is just a particular ordering of symbols. In Sudoku it is insisted that there is only one occurrence of each symbol (or number) in each group (row, column or region).

So for two symbols there are only two possible orders {1;2} and {2;1} with three there are six {1;2;3}, {1;3;2}, {2;1;3}, {2;3;1}, {3;1;2} and {3;2;1} possible orders and for four there are 24 permutations of the four symbols. The number of permutations is the Factorial of the number of symbols in the set, as each time an extra element is added to a set of size 'n' that element multiplies up the number of arrangements of the previous set size. So for the standard Sudoku set size of 9 we have 9 factorial (represented in maths as 9!) or 9x8x7x6x5x4x3x2x1 possible permutations which works out as 362,880 possible ways of ordering the nine symbols in a row, column or region.

Properties of permutations

On their own permutations do not look at all exciting. But when you have a permutation you can create other permutations from it by doing one of the following:

Swap the symbols consistently
In a permutation you can always swap all occurrences of one symbol for another as long as the swap is done systematically and in reverse too. If you swap 4 with 1 then the 1 must be swapped to a 4 (e.g. 4;2;3;1 would become 1;2;3;4). Several or all symbols can be swapped in this way. The result will always be a valid permutation.

Here is a 4x4 puzzle with 1;2;3 swapped for 3;1;2 respectively, they are both valid 'Sudokus'.

Shifting the order
Permutations are by their nature just an ordering so you can swap the order of elements however much you like and the result is also a permutation. For example you can shift the symbol '8' from the start to the end so (8;4;5;6;1;2;7;9;3) becomes (4;5;6;1;2;7;9;3;8) or swap each element with its neighbor in pairs so (8;4;5;6;1;2;7;9;3) becomes (4;8;6;5;2;1;9;7;3).

Here is a 4x4 puzzle with the bottom two rows swapped, they are both valid 'Sudokus'.

Arithmetic Analysis

The original related puzzle of Magic squares has the property that all the numbers in rows and columns add up to the same number.

This is also a property of permutations, if you add up the individual numbers in the set that make up the permutation then this will always give the same result. This is because addition is Associative, it does not matter in which order you add up the numbers, you always end up with the same result ((5+1)+2) = (5+(1+2)). The same is true of multiplication but it is not true of all the simple arithmetic operations. Both subtraction and division give different results depending on the order that the operations are carried out, e.g. (4 / 3) / 2 is not the same as 4 / (3 / 2).

If we add up all the numbers in a completed 9x9 Sudoku row, column or region the answer is always the same: 45, and if they are multiplied together the answer is always 362,880 (this is our 9 'factorial' or 9!)

This is starting to look useful because if we had a number missing it can be deduced which one it is. For example, if there is one number missing and the sum of the other numbers is 40 the missing number must be a '5' to make up the total for the group of nine of 45. This does not work in general as, for example, if two numbers are missing and the total is 38, it can't be directly deduced what the numbers are, it could be any two numbers that add up to 7 (either 2 and 5; or 1 and 6; or 3 and 4). Similarly with multiplication, the value of missing number this can be deduced by multiplying together all the numbers that are there and dividing this product into 362,880. For example if the group is 8;4;6;1;2;5;9;3 the product is 51,840 so dividing this into 362,880 we get the answer '7' as the missing number. Unfortunately, just like addition we can't use this scheme to determine which of two or more numbers are missing. There is more than one choice of numbers that give the same answer.

Here are the factorials from 1 to 9 (9!).

Before getting any further into any more theoretical analysis, let's simplify by using the 4x4 Sudoku grid rather than 9x9 just to reduce the number of options. In the 4x4 grid, the rules are just the same but there are only the four numbers 1, 2, 3 and 4 in each row, column and region. So a permutation of all the numbers must add up to 10 and the product of all the numbers is 24 (4! factorial). [Sudoku Dragon supports ten different puzzle sizes including the 4x4 and 16x16 sized puzzles.]

Gödel numbers

The problem with deducing missing numbers does not arise if we use a form of Gödel numbers. Here we don't just multiply the Sudoku numbers together we use the corresponding prime number. So for a '1' we use the first prime number '2', for '2' use the second prime '3'; for '3' use '5'; for '4' use '7' and so on.

All Sudoku groups in the 4x4 grid must now multiply up to give a product of 2x3x5x7 = 210 rather than 24. If a Sudoku 4x4 group is 2;;3;; with two missing numbers we convert these to the corresponding prime and multiply them together 3 x 5 giving 15. Now 210 / 15 = 14. So the two missing numbers multiplied together must give 14 and there are only two numbers that can do that 2 and 7. Using the corresponding 'encoding' table shows that '1' (for the 2) and '4' (for the 7) are the missing numbers. We can use this trick for finding any number of missing numbers in a Sudoku group (of any size) just by a little multiplication and division. Why does this work? Because prime numbers are well, prime, we can't make a prime number by multiplying two other numbers together.

Note : the product of all primes up to a specific prime number such as 210 is given a special name : a 'primorial'.

In the case of 9x9 grid we need the next five prime numbers for '5' use '11'; for '6' use '13'; for '7' use '17'; for '8' use '19' and for '9' use '23'. So to work out what is missing from an incomplete row of 8; 4; 6; 1; 2; 5; 9; 3 we convert these to the corresponding prime and multiply them together 19x7x13x2x3x11x23x5 = 13,123,110 but the product of all the numbers must be 223,092,870 (primordial for 9) which means the missing number is 17 or back in the normal Sudoku world '7'.

Now try a Sudoku group with three numbers missing 9;3;;6;;1;;2;8 the Gödel number using our encoding gives 170,430 dividing this into the full product 223,092,870 gives an answer of 1,309. Now because of the properties of prime numbers there is only one way of generating 1,309 using only prime numbers and that is by multiplying 7 x 11 x 17, and so the missing numbers must be the corresponding numbers 4, 5 and 7.

More logical Approach

Having looked at traditional 'arithmetic' to investigate the properties of Sudoku it is worth looking for a much simpler analysis. Sudoku can be done with any old symbols not just numbers, they can be colors, shapes, pictures: anything as long as they are distinct and there is only one in each group. We shouldn't get hung up about using 'numbers', the problem is more general than that. What is needed then is just a simple 'yes' or 'no' approach, to the question 'is the symbol at this position?'. This can then be easily encoded into a binary '0' or '1'. For the 4x4 grid we can then encode the permutation of 3;4;1;2 as four binary numbers: 0100 (for position 1 there is a 3);1000 (for position 2 there is a 4);0001 (for position 3 there is a 1) and 0010 (for position 4 there is a 2). We put a binary '1' to indicate the presence of the symbol at the corresponding position. To be a well formed Sudoku group the binary combination logical or of all these numbers must give a result of 1111 to confirm that each of the four symbols has occurred once in all four positions in the group. This can then be used to find missing numbers, a group with 2;;3;; would be translated as 0010;;0100;; logically ored together gives 0110, so we can now tell at a glance that it is a '4' and a '1' that are the missing numbers as they correspond with the missing symbols represented by '0's. So rather than using Gödel numbers the same can be applied to Sudoku much more easily using boolean 'yes/no' operations.

Actions and Operations

There is another way of looking at permutations and symbols. You can think of the contents not as symbols but as operations to perform. A permutation is just saying that you need to perform a set of operations only once but in any order. To make this more everyday consider four operations : getting dressed; brushing hair; collecting the post and eating breakfast. We might do each of these once every morning, and they can be done in any order. If you think of these as a permutation with numbers 3;2;4;1 might represent collect post; brush hair; eat breakfast; get dressed. That's established the idea of thinking of a permutation as a sequence of operations done in time order rather than symbols. Looking at this in a simpler, more mathematical sense we could treat each symbol as a move along a vector. An 'operation' is in terms of moving a certain amount in a certain direction. So we could use '1' as move 2 units N ; '2' as move 2 units S; '3' as move W 2 units and '4' move E 2 units. These are chosen so that the end result of completing all these steps takes you back to where you started. This is important as it makes the sequence of operations into a mathematical concept known as a 'ring' in group theory. Other examples of these sorts of patterns are square dances where after a number of moves, twists and turns you end up where you started. Other vectors could have been chosen. Just like addition the moves can be done in any order to achieve the same end position. Interestingly this approach allows missing moves to be deduced by just combining the known moves and working out how to get back to the original point.

Combining permutations

If Sudoku were just a matter of single groups of symbols then it wouldn't be much of a challenge. The complexity comes from applying the restriction of a single group into a two dimentional grid. There are then three constraints on each squares: it must be unique to the row; column and region.

Sudoku Possibility Analysis

Apart from the simplest cases (where only one choice is available) the solving of a Sudoku puzzle involves analysing permutations. Each unsolved square can have one or more possibilities. Each unsolved symbol must be possible in one or more square in a group.

If we look at a Sudoku group on its own then all the unused symbols can occur in any of the unsolved squares. However taking the other groups that share squares with this group reduces the number of possibilities. So for a row having 7; ; ;6;3; ; ;2;5 the four missing numbers are 1;4;8;9 these could on their own occur in any permutation within the squares. Other groups (columns, regions) may, for example. constrain the choice down to {1;4;8}, {1;8;9}, {4;8} and {1;4;8;9} for the four empty squares. Each of these is a subset of the missing numbers (1;4;8;9) and it is the pattern of these subsets that are used to deduce additional constraints on the possible content of the squares. For example, if the possibility subsets were {1;8} {1;8} {4;8;9} and {4;9} then {1;8} is an example of a 'naked twin', there are two squares with just two possibilities and this means that the '1' must go in one of the two places and '8' in the other place. Therefore the square with {4;8;9} as possibilities can be safely restricted down to {4;9} as the '8' can't occur there. This is the simplest case of how analysis of possibilities can be helpful in reducing the number of possibilities. By using the knowledge that a symbol may occur only in a subset of the squares we can deduce not where exactly it can go but deduce where it cannot go.

General possibility rule

The 'naked twin' rule is just the simplest example of a general rule for Sudoku possibilities. The rule is that if there are 'n' symbols and all possibilities for these symbols are located in a subset of the 'n' squares within a group then we have a sub-group of possibilities. Apart from the twin example there is the 'chain'. If the possibilities were {1;4} {4;8} {8;1} and {1;4;9} then the first three form a chain of the symbols {1;4;8} and preclude the occurrence of these symbols in the last square, in this case the last square becomes a 'single possiblity' square as it must be '9'. A chain is a closed loop of symbols that imply that the symbols must occur only in this group but it can not be determined where precisely the numbers go. In the case of {1;4} and {4;1} in a group this is just saying the allocation is either {1} and {4} or {4} and {1} so the 1 and 4 can not occur anywhere else. The same logic applies to 3 or more symbols it is not limited to just two. If we had {1;4;9} {1;4;9} {1;4;9} and {4;8} then the three squares form a triplet of {1;4;9} and the other square must be the 8.

In this example taken from a 9x9 grid, one region has two naked twins {4;5} in the top row. By the twin rule 4 can not therefore occur in the four other unallocated squares and 5 in three of the remaining squares. This makes it a very useful rule.

Beyond the linear dimension

Much of this analysis so far has looked at one Sudoku group in isolation. Each square is a member of three groups (row; column and region) and so the constraints for the square in one group apply equally to the other groups. So if a column requires that {1;4;9} are the possibilities for a square in the column and the row it is in gives {2;4;9} as possibilities for the same square then the combined constraint is that the square can only be 4 or 9 {4;9}. If in addition the region gives possibilities {3;4;5} then that would only leaves {4} as the only possibility that meets the requirements of the row; column and region. The knowledge that a {4} must go in the square can be fed back into the constraints for the three groups as it precludes {4} being a possibility anywhere else in the groups.

The complication does not end there. Some of the constraints are 'indirect' meaning that the implication for one square will limit what can go in another square, but because of the shared groups it is in. The simplest example of this is the X-Wing. Here four groups are logically inter-linked to form a 'box'. If the possibilities form a particular pattern then the corners of the box must be in one of only two configurations. The Sudoku rules are applying a two-dimensional constraint involving four groups (two rows and two columns). This can become even more complicated as even more groups can become involved... These cyclic dependencies result from the ways that squares are connected via groups into grids. Both humans and computers struggle to find these interdependencies between possibilities. Luckily most Sudoku puzzles can be solved without resorting to using them.

Computing a solution

Finding patterns within these permutation subsets is definitely a 'hard' problem. This is not just a human description, it is just as tough for computers too. Pattern matching problems like Sudoku belong to the class of the difficult problems to solve : The NP complete class. This is because any analysis has to look through all the possible combinations, it cannot do it as a single linear scan of the permutations. To spot a 'twin' a computer needs to look through all possible combinations of two squares in a group. The time taken to solve does not grow linearly with problem size it grows exponentially. If it takes 2 seconds to solve a problem of size '3' it will take much more than 4 seconds to solve a problem of size '6'. There is no simple 'trick' that a human or computer can use to solve Sudoku puzzles in general.

The simplest algorithm is the trial and error method which checks all the possibilities in turn without looking for excluded possibilities or only choices. This can take a very long time to do as there just so many to check - the crudest algorithm would work through something like 10 to the power 47 combinations (that's 10 with 47 noughts after it).

Hardest Sudoku Puzzle

There are many claims for the most difficult Sudoku puzzle ever discovered. Some of these are just permutations of the same fiendishly difficult puzzle. To be hard to solve the puzzle must reveal the minimum number of squares and still have a unique solution. There are many examples of puzzles that are not 'solvable' without making a guess on the content of the square. This is difficult to determine as there are an indefinite number of advanced solution strategies available that need to be tried before being certain that this is the case. Here is an example of a truly difficult standard puzzle that you might like to try to solve. You will notice is it not symmetric and so can be considered not a valid puzzle, but if you relax the requirement for symmetry harder puzzles can be created. The puzzle has only 21 revealed squares.

 To download this puzzle  click here

Many puzzlers reckon that having a large empty space in the middle creates very tricky puzzles. If so then surely this must qualify as one of the hardest possible puzzles to solve. It has 22 revealed squares. It is reckoned that the hardest possible Sudokus have 17 or 18 'given' or initially revealed squares.

 To download this puzzle  click here

Sudoku Puzzle Sizes

The 4x4 Puzzle

There is nothing that special about 9x9 Sudoku puzzles, it turns out that to make an interesting Sudoku puzzle that can be solved in a reasonable time 9x9 is a good choice. However it is possible to choose a smaller or larger size of grid.

With 4x4 there are only 16 squares in total and it is impossible to create a difficult puzzle. The minimum number of squares that can be revealed and still produce a solvable puzzle is four. I have never seen a 4x4 with only 3 initial squares revealed - this may be provable to be an impossible starting arrangement.

The 16x16 Puzzle

Moving to larger than the regular 9x9 puzzle size introduces nothing new other than more possibilities to work through. All the strategies you might use for solving 9x9 can be adapted to the larger 16x16 grid. For example the 'two out of three' strategy becomes the 'three out of four' strategy. You can still use all the basic strategies : only choice, single possibility, only square, excluded twins, naked twins, excluded subgroup, X-Wing and all the advanced strategies. It becomes much harder for mere humans to solve when there are 16 rather than 9 numbers/symbols to reason about. But with practice these grids can become quite straightforward to solve too.

Larger Sudoku Puzzles

There is no theoretical limit on the size of a Sudoku puzzle. The rules are generic and by mathematical induction it can be shown that they can just grow and grow. To keep to a square arrangement the number just goes up in squares : 16x16; 25x25; 36x36 (over a thousand squares to complete); 49x49; 81x81; 100x100 (10,000 squares in the puzzle).

Rectangular Puzzles

If you have a set of same sized rectangles you can arrange them into a square grid. One rectangular Sudoku is 3x5 blocks arranged as three blocks wide and five blocks deep giving 15 regions in all. The same can be done with many other sizes (e.g. six 2x3 blocks), in fact the only grid sizes that can't be used are those that are prime numbers and so can't be divided up into a rectangular block (e.g. a 5x5 puzzle can not be created). Sudoku Dragon supports 2x3, 2x4, 3x5, 3x5, 4x5, 2x5 and 2x7 rectangular block puzzles giving puzzle sizes of 6, 8, 15, 20, 10 and 14 respectively.

Please refer to our Theme and Variations page for some strange and interesting forms of Sudoku that are widely available.

Here is an example of a 14x14 grid made up two stacks of 2x7 squares. The symbols used are 0 to 9 and A to D

The Smallest Sudoku Puzzle

For the pure mathematicians amongst you, it may be interesting to note that from a pedantic point of view 4x4 is not the simplest size of Sudoku puzzle. If instead of all groups having 4 squares in it we have just 'one' square then, even though it is rather academic, the 1x1 sudoku puzzle has 1 row and 1 column with 1 symbol occurring just once in each row and column. There is only one region with 1 square in it. So there is only one Sudoku puzzle of size 1 and the solution is 1. Mathematicians may appreciate the symmetry as it shows that the Sudoku rules are general for any group size including 1 upwards. It just happens that 1 is a seriously simple puzzle to solve!

If you found this page useful please consider making a donation to keep this web site flourishing. To donate, please click here

Give our SudokuDragon puzzle solver a free 23 day trial by visiting our download page. All the main Sudoku strategies have clear, easy to follow guide tutorials. It can selectively help you quickly identify possibilities and exclude the ones that actually are impossible.

Any comments on this page ? Click here to contribute

Copyright © 2005-2009 Sudoku Dragon