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 there must be 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 group, 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 9x 8x 7x 6x 5x 4x 3x 2x 1 possible permutations which works out as 362,880 possible ways of ordering the nine symbols in a row, column or region.

Properties of permutations

Permutations do not look at all exciting; but from it you can create other permutations 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 Sudoku puzzles.

Shifting the order
Permutations are just an ordering so you can swap the order 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 Sudoku puzzles.

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

This is also a property of permutations, if you add up the individual numbers in the permutation set then this will always give the same total. 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; as 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 9 factorial or 9!)

This starts 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 5 to make up the required group total 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 two 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 one missing number can be deduced by multiplying them together and dividing the 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 not 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 analysis, let us use the simpler 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 four numbers (1, 2, 3 and 4) in each group (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 2x 3x 5x 7 = 210 rather than 24. If a Sudoku 4x4 group contains just {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 prime number is 17; back in the normal Sudoku world this is 7.

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

More logical Approach

Having looked at traditional mathematics to investigate the properties of Sudoku it is worth looking for a different and thankfully 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 should not get hung up about using numbers, the puzzle is more general than that. What is needed then is just a simple 'yes' or 'no' answer 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 or-ed 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 0s. So rather than using Gödel numbers the same can be applied to Sudoku much more easily using boolean 'yes/no' questions.

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. Just like addition the moves can be done in any order to achieve the same end position. 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. Applied to Sudoku this can be used to work out which numbers are missing.

Combining permutations

If Sudoku were just a matter of single groups of symbols then it would not be much of a challenge. The complexity comes from applying the restriction of a single group into a two dimensional 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) solving a Sudoku puzzle involves analyzing permutations. Each unsolved square can have one or more possibilities. Each unused symbol must be possible in one or more squares 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 containing {7; ; ;6;3; ; ;2;5} the four missing numbers are {1;4;8;9} which can occur in any permutation within the squares. Other groups (columns, regions) may, for example. reduce the choice down to {1;4;8}, {1;8;9}, {4;8} and {1;4;8;9} in 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 these 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 not occur there. This is the simplest case of how analysis of possibilities can be helpful in reducing the options. By using the knowledge that a symbol may occur only in a subset of the squares we cannot deduce where exactly it can go but deduce where it cannot go.

General possibility rule

The naked twin rule is just one 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 'n' squares within a group then we have a sub-group of possibilities. Apart from the twin example there are also chains. 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 possibility' 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 8 as 4 must be allocated within the triplet.

In this example taken from a 9x9 grid, one region has a naked chain {1; 7; 9} in the top row. Using the chain rule 1; 7 or 9 can not occur in the two other unallocated squares as a 9 occurs in both of the remaining squares, making 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 the rules for 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 that square then the combined constraint for the square is just 4 or 9 {4;9}. If the region it is in gives possibilities {3;4;5} then that would 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 these groups as well.

The usefulness 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) because of the X-Wing. 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 interconnected grids. Both humans and computers struggle to find these inter-dependencies between possibilities. Luckily most Sudoku puzzles can be solved without needing to work them out.

Computing a solution

Finding patterns within these permutation subsets is definitely a hard problem to solve. This is not just for humans, 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. 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 NP complete problems 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 far longer than 4 seconds to solve a problem of double the size. There is no simple 'trick' that a human or computer can use to solve Sudoku puzzles in general, if you find a way you will become a multi-millionaire.

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

Hardest Sudoku Puzzle

What is the most difficult Sudoku puzzle ever discovered? To be genuinely hard to solve a 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 having to make a guess on the content of the square. This is difficult to determine as there are a 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. It is not symmetric and so can be considered not a valid Sudoku. The asymmetry can make puzzles harder to solve. The puzzle has only 21 revealed squares.

To download this puzzle and
see it in Sudoku Dragon  click here...

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

To download this puzzle and
see it in Sudoku Dragon  click here...

Sudoku Puzzle Sizes

The 4x4 Puzzle

There is nothing all that special about 9x9 Sudoku puzzles, it just happens to make an interesting Sudoku puzzle that can be solved in a reasonable time. 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 hidden twins, naked twins, excluded sub-group, 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 just grow and grow. Keeping 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

A set of same sized rectangles can be arranged into a square puzzle grid. One rectangular Sudoku is made up of 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 subdivided in any different way). 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.

This 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

Please refer to our Theme and Variations page for more strange and interesting forms of Sudoku.

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!

See also
Sudoku Solvers A range of mathematical puzzles and solvers.

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

Any comments on this page ? Click here to contribute

Copyright © 2005-2013 Sudoku Dragon