Sudoku Quest - MSN Games - Free Online Games Genre: Card & Board Fill in the blanks with logic and reasoning – no math required! Fill in the blanks so that every number from 1-9 appears in each of the nine columns, in each of the nine horizontal rows and in each of the nine 3x3 boxes that make up the grid. Numbers can only be used once in each row, column or box. Select a blank square by left-clicking on it. Enter a number between 1 and 9. If it turns red it is a duplicate; if it turns blue it could be correctly placed. If you're not sure of an answer you can "pencil in" numbers by holding down the space bar, left-clicking the mouse and then typing in the required number from 1 to 9. Solve the puzzle by filling all the squares in the grid with numbers. Every horizontal row, vertical column and 3x3 box should contain the numbers 1 thru 9 with no duplicates.

Anything but square: from magic squares to Sudoku | plus.maths.org Anything but square: from magic squares to Sudoku By Submitted by plusadmin on March 1, 2006 March 2006 What is a magic square? There is an ancient Chinese legend that goes something like this. Some three thousand years ago, a great flood happened in China. In order to calm the vexed river god, the people made an offering to the river Lo, but he could not be appeased. Each time they made an offering, a turtle would appear from the river. One day a boy noticed marks on the back of the turtle that seemed to represent the numbers 1 to 9. The numbers were arranged in such a way that each line added up to 15. Hence the people understood that their offering was not the right amount. Nymph of the Lo River, an ink drawing on a handscroll, Ming dynasty, 16th century. Freer Gallery of Art The markings on the back of the turtle were in fact a magic square. A magic square is a square grid filled with numbers, in such a way that each row, each column, and the two diagonals add up to the same number.

Here's what the magic square from the Lo Shu would have looked like. It has three rows and three columns, and if you add up the numbers in any row, column or diagonal, you always get 15. The Lo Shu magic square Mathematical properties When mathematicians talk about magic squares, they often talk about the order of the square. This is just the number of rows or columns that the magic square has. For example, a 3 by 3 magic square has three rows and three columns, so its order is 3. In a typical magic square, you start with 1 and then go through the whole numbers one by one. For example, a magic square of order 3 contains all the numbers from 1 to 9, and a square of order 4 contains the numbers 1 to 16. Not surprisingly, magic squares made in this way are called normal magic squares. In the Lo Shu magic square, which is a normal magic square, all the rows, all the columns and the two diagonals add up to the same number, 15. We call this number the magic constant, and there's a simple formula you can use to work out the magic constant for any normal magic square.

For a magic square of order n, the magic constant is M(n) = n(n2+1)/2. So, for a square of order 3, we have M(3) = 3(32+1)/2 = 15 It is easy to derive this formula: a magic square of order n has exactly n rows, and each row adds up to the magic constant M(n). So nM(n) is the value you get when you add up all the entries in the square. But since every number between 1 and n2 appears exactly once in the square, you know that the total number is also equal to 1+2+3+ ... + n2. And, as many of you may know, this sum is equal to n2(n2+1)/2. Putting all this together, you get nM(n) = n2(n2+1)/2, so M(n) = n(n2+1)/2. It turns out that normal magic squares exist for all orders, except order 2. There's only one magic square of order 1 and it isn't particularly interesting: a single square with the number 1 inside!

You can work out for yourself why the square of order 2 does not exist. Mathematicians normally regard two magic squares as being the same if you can obtain one from the other by rotation or reflection. Counted in this way, there is only one magic square of order 3, which is the Lo Shu magic square shown above. There are 880 distinct magic squares of order 4 and 275,305,224 of order 5. Nobody knows how many distinct magic squares exist of order 6, but it is estimated to be more than a million million million! De La Loubere and the Siamese Method You might now be wondering whether there is an easy way to make a magic square without resorting to guesswork. Luckily, there is. De La Loubere was the French ambassador to Siam (now Thailand) at the end of the seventeenth century. On his return to France he brought with him a method for constructing magic squares with an odd number of rows and columns, otherwise known as squares of odd order. Begin by finding the middle cell in the top row of the magic square, and write the number 1 in it.

Continue writing the numbers 2, 3, 4, and so on, each in the diagonally adjacent cell north-east of the previously filled one. When you reach the edge of the square, continue from the opposite edge, as if opposite edges were glued together. If you encounter a cell that is already filled, move to the cell immediately below the cell you have just filled, and continue as before. When all the cells are filled, the two main diagonals and every row and column should add up to the same number, as if by magic! Here is a partial construction of a 5 by 5 magic square. Starting from 1, I have filled in the numbers up to 10. There is no space northeast of the 1, so I have put the 2 in the bottom row, followed by the 3. Again, because the 3 is on the edge, the 4 goes on the opposite side. The 6 should go in the cell where the 1 is, but because this cell is occupied, I put the 6 immediately below the 5 and continued up to 10. Try completing the square and then try making some of your own.

While this, known as the Siamese method, is probably the best known method for making magic squares, other methods do exist. The German schoolmaster Johann Faulhaber published a method similar to the Siamese method before it was discovered by De Le Loubere. Another way is the Lozenge method by John Horton Conway , a prolific British mathematician. Proving that these methods work can be done using algebra, but it's not easy! Magic squares of even order Although the Siamese method can be used to generate a magic square for any odd number, there is no simple method that works for all magic squares of even order. Fortunately, there is a nice method that we can use if the order of the square is an even number divisible by 4. (For those that are interested, the LUX method was invented by J. H. Conway to deal with even numbers that are not divisible by 4). Instead of saying "numbers that are divisible by 4", mathematicians usually say "numbers of the form 4k". For example, 12 is of the form 4k, because you can replace k with 3.

Using the same idea, numbers that give a remainder of 2 when you divide them by 4 can be called numbers of the form 4k + 2. So start by picking the order of the square, making sure that it's of the form 4k, and number the cells 1 to (4k)2 starting at the top left and working along the rows. Then split the square up into 4 by 4 subsquares, and mark the numbers that lie on the main diagonals of each subsquare. In the example, these are the coloured numbers; the order of the square is 4, so the only 4 by 4 subsquare is the square itself. Now switch the lowest marked number with the highest marked number, the second lowest marked number with the second highest marked number, and so on. Another way of saying this is that if the magic square has order n, swap the numbers that add up to n2 + 1. In this particular example, the order is 4, so we have to swap the numbers that add up to 17: 1 and 16, 4 and 13, 6 and 11, 7 and 10.

If you flip this magic square over, it is identical to the one drawn by the famous German artist, Albrecht Dürer. You can see it in the corner of his engraving Melencolia. Albrecht Dürer's 1514 engraving Melencolia. The magic square appearing in Melencolia shown in close-up. Here is an example of an 8 by 8 magic square constructed using the same method. The square was split into four 4 by 4 squares, and the diagonals were coloured. The coloured numbers that add up to 65 were switched: 1 was swapped with 64, 4 was swapped with 61, and so on. A Knight's Tale As any chess player will know, an order 8 magic square has the same number of cells as a chessboard. This similarity means that we can create a special type of magic square based on the moves of a chesspiece. The knight is an interesting piece, because unlike the other pieces, it does not move vertically, horizontally or diagonally along a straight line. Instead, the knight moves in an L-shape as shown in the diagram.

But is it possible for a knight that moves in this way to visit every square on the chessboard exactly once? The knight (K) can move in an L-shape to any of the squares marked with an X One of the first mathematicians to investigate the knight's tour, as the problem has become known, was the great Swiss mathematician Leonhard Euler . His work inspired others to take up the challenge. Using the concept of the knight's tour William Beverley managed to produce a magic square, as shown below. Cells are numbered in sequence, as the knight visits them. Although the rows and columns all add up to 260, the main diagonals do not, so strictly speaking it is a semi-magic square. In fact, a magic square based on a knight's tour is often called a magic tour, so what Beverley produced in 1848 is a semi-magic tour! At first glance, it seems that the following magic square by Feisthamel fits the bill. The rows, columns and diagonals all sum to 260. Unfortunately, it is only a partial knight's tour, as there is a jump from 32 to 33.

So when is it possible to turn a knight's tour into a magic square? In 2003, Stertenbrink and Meyrignac finally solved this problem by computing every possible combination. They found 140 semi-magic tours, but no magic tours. Checkmate! Latin Squares Latin squares are the true ancestors of Sudoku. You can find examples of Latin squares in Arabic literature over 700 years old. They were discovered by Euler a few centuries later, who saw them as a new type of magic square, and it's thanks to him that we call them Latin squares. Latin squares are grids filled with numbers, letters or symbols, in such a way that no number appears twice in the same row or column. The difference between a magic square and a Latin square is the number of symbols used. For example, there are 16 different numbers in a 4 by 4 magic square, but you only need 4 different numbers or letters to make a 4 by 4 Latin square. Here's an example of a Latin square, with the numbers 1 to 4 in every row and column.

If you look at the first row and the first column, you'll notice that the numbers occur in sequence: 1, 2, 3, 4. When this happens, we say that the Latin square is in standard form or normalised. Any Latin square can be turned into standard form by swapping pairs of rows and pairs of columns. There is only one normalised Latin square of order 3, and there are only 4 distinct ones of order 4, but a staggering 377,597,570,964,258,816 of order 9. In 1979 J.R. Nechvatal worked out a complicated formula giving the number of distinct normalised Latin squares of any order. To this day no-one has been able to derive from this, or any other formula, how fast this number grows as the order of the square gets large. If we combine the two Latin squares below, we get a new square with pairs of letters and numbers. No pair is repeated, but the grid contains every single combination. We call this new square an Euler Square or a Graeco-Latin Square, and the two squares that formed the Euler square are called mutually orthogonal.

+ = Latin squares and Euler squares have a wide variety of applications within and outside of mathematics, including experiment designs and organising round-robin tournaments. For instance, let's suppose that Albert the scientist wants to test four different drugs (called A, B, C and D) on four volunteers. To make it a fair test, he decides that every volunteer has to be tested with a different drug each week, but no two volunteers are allowed the same drug at the same time. Saying that each row represents a different volunteer and each column represents a different week, Albert can plan the whole experiment using a Latin square. The Thirty-Six Officers Problem Euler did a considerable amount of work on Latin squares, and even came up with some methods for constructing them. Euler easily found methods for constructing odd-order Graeco-Latin squares and squares for which the order is a multiple of 4, but he could not produce a Graeco-Latin square of order 6. He even posed a famous problem which could only be solved by making a Graeco-Latin square of order 6.

The problem of the 36 officers goes like this: is it possible to arrange six regiments, each consisting of six officers of different ranks, in such a way that no row or column contains two or more officers from the same regiment or with the same rank? Euler never solved this problem. In fact, he believed that it was impossible to make a Graeco-Latin square if the order is of the form 4k + 2. Just over a hundred years ago, Euler's prediction was partly proved right. A French mathematician called Gaston Tarry checked every possible combination for a 6 by 6 Euler square and showed that none existed. Finally in 1960, Bose, Shrikhande and Parker managed to prove that Euler squares exist for all orders except 2 and 6. But bearing in mind that they had computers at their disposal, spare a thought for Tarry who had to do everything by hand! Leonhard Euler Sudoku If you catch a train in London, you'll see plenty of commuters with a pen in their hand, a newspaper on their lap and one thing on their mind — Sudoku. Sudoku or Su Doku are a special type of Latin squares.

They are usually 9 by 9 grids, split into 9 smaller 3 by 3 boxes. The aim of the game is to fill every cell with one of the numbers from 1 to 9, so that each number appears exactly once in each row, column and 3 by 3 box. To help you complete the puzzle, a few numbers are already given as clues. The person credited with the invention of Sudoku is Howard Garns. The first puzzle appeared in the magazine Dell pencil puzzles and word games in 1979 and was called Number Place. The puzzle gained popularity in Japan during the 1980s, and was picked up in 2004 by the British newspaper The Times. Sudoku is Japanese for single number and the name is now a registered trademark of a Japanese puzzle publishing company. It's difficult to tell how many distinct completed Sudoku grids there are, but mathematicians Bertram Felgenhauer and Frazer Jarvis used an exhaustive computer search to come up with the number 6,670,903,752,021,072,936,960, which was later confirmed by Ed Russell.

Solving Sudoku requires logical thinking and a systematic approach. Normally, sufficiently many numbers are given as clues in the initial grid — the one you start the puzzle with — to ensure that there is only one solution. The more numbers are filled in initially, the easier the puzzle becomes of course. So real Sudoku addicts probably prefer a small number of initial clues. But what is the minimal number of clues that have to be given to ensure that there is exactly one — and no more — solution? This is a good question, and one that so far mathematicians have been unable to answer, though there is good reason to believe that the number is 17. And what if we turn this question around? Given an individual completed grid, how many minimal initial grids are there which have this grid as a solution? Here we mean those initial grids from which no more number can be removed without making several solutions possible. Again, mathematicians do not know the answer to this question. But let's have a look at how to go about solving a Sudoku puzzle. Here's one I created to illustrate one of the basic techniques, known as scanning.

Looking at the middle three boxes, we have a 3 in the left-hand box and one in the middle box, but we still need to put a 3 in the right-hand box. So where should it go? Well, it can't go in the top row, because there's already a 3 in that row. For the same reason, it can't go in the bottom row, which leaves the middle row. There's only one free cell in the middle row, so the 3 has to go in it. The middle three boxes Now if we look at the bottom three boxes, one of the rows already has 6 numbers. I've called the empty cells A, B and C (in order from left to right), and the numbers that are missing are 3, 7 and 8. If you look at cell C, the only number that can go in it is 7. That's because the column that C lies in already contains 3 and 8. Finding A and B is now pretty simple. There's already a 3 in the same column as B, so B has to be 8. That means A must be 3.

Solving the rest of the puzzle is a bit trickier, but well worth the effort. The bottom two rows The Sudoku craze has swept across the globe, and it shows no signs of slowing. Several variations have developed from the basic theme, such as 16 by 16 versions and multi-grid combinations (you can try a duplex difference sudoku in the Plus puzzle ). But as with magic squares and Latin squares, the popularity of Sudoku will depend on whether they can continue to offer new challenges. About the author Hardeep Aiden is a graduate of the Department of Mathematics at Imperial College, London. Apart from mathematics, he is interested in languages and linguistics, and is currently learning Japanese, French and British sign language. Sudoku Puzzle Theory Read More Sudoku Puzzle Theory Sudoku is all about permutations, well 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 fast 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 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-2016 Sudoku Dragon

Question: The game of Sudoku involves filling in squares with what numbers?
Answer: 1 to 9