Sudoku Puzzle Introduction

Sudoku is not a numerical puzzle, as many people may initially think. Sudoku consists of a square grid to be filled in with symbols. The symbols are usually the numbers 1 to 9 and that is why it is often called numerical but they may as well be letters or colours or shapes or... whatever as long as they are distinct symbols.

There is just one simple rule controlling where you can place symbols in the grid. A symbol must occur once and only once in each group of nine squares. The groups of nine squares include the rows, columns and regions within the grid. Such a simple rule leads to an amazing variability of complexity of the Sudoku puzzles.

[Sudoku in Japanese]

Sudoku Terminology

First let's introduce the terms we will use on the Sudoku Dragon web site, not everyone uses the same convention.

The whole puzzle area we call the grid, it is divided into rows (horizontal lines) and columns (vertical lines) made up of individual Sudoku squares.

Rows

To save confusion we use letters rather than numbers to refer to rows and columns. The names are shown at the heading of the grid. In this example Sudoku grid row C (capital C) is highlighted. If we used numbers we'd end up having to say things like in row 3 there is only one place for a 5 while in column 2 there are 3. Confusing isn't it ? Using letters for grid references makes this a lot less confusing.

Similarly Sudoku columns are given a lower case letter.
Column e (small e) is highlighted.
Using row and column letters lets us unambiguously refer to squares. For example He is row H column e, there is a 2 allocated in this Sudoku square.

We use the term region for a set of nine adjacent Sudoku squares for example the top left region including square Aa.

The whole grid has nine of these regions. Some other Sudoku sites may use the term 'mini-grid'; 'box' or 'subgrid' for 'region' but we think region is simpler and easier. A symbol must occur once and once only in each of the regions within the grid as well as each row and column. This was one of the main innovations that make Sudoku such an interesting puzzle to solve.

The process of solving a Sudoku puzzle is 'simply' to fill in all the empty squares. However each square has one unique solution as it must obey the rule of Sudoku : Each row, column and region must contain one and only one of the numbers 1 through 9.

Sometimes it is obvious what must go in a square while for others a great deal of mental torture is involved in working through all the possibilities (it can take half an hour to solve one square!). Much like placing a single piece in a jigsaw, there must be a place to fit it in somewhere but sometimes finding the place is easy to spot and sometimes it takes an age.

There is no correct sequence of square allocations to make, different people have there own techniques for solving the Sudoku puzzle and will tackle the squares in different orders. However, the end result is always the same, there is only one unique solution.

Making mistakes

If you make a mistaken allocation of a number for a Sudoku square this will make the puzzle unsolvable. At some later stage you will find an insurmountable contradiction, a symbol would have to be placed in two squares in the same row, column or region violating the Sudoku rule or else you'll find a square that can take no number at all according to the rules. To correct the mistake you need to backtrack through the allocations that you have made until you find the one in error. Often it's because you overlooked another possible square and thought it was the only choice. Sudoku Dragon helps with this as it immediately alerts you when a puzzle becomes unsolvable or you make an allocation that breaks the Sudoku rule. You can easily backtrack to a solvable state again.

There are a number of standard 'rules' that people have found to be useful in solving a Sudoku puzzle. There are tutorials built into the Sudoku Dragon program demonstrating the use of these rules.

Only choice rule

There may be only one possible choice for a particular Sudoku square. In the simplest case you have a group (row, column or region) that has eight squares allocated so that leaves only one remaining choice available. So this number must be allocated in that free square.

Looking at the row B all the squares except the first square Ba have been allocated so the missing number 4 has no choice but to go in the Sudoku square Ba.

Sometimes rather than a Sudoku square having only one choice for it, a Sudoku group may have one square in which only one number can possibly be allocated. For example if a group has seven squares allocated with only two numbers left to allocate it is often the case that an intersecting (or shared) group will mean that a number can not go in one of the squares and so it must go in the other.

In this case the highlighted column c has seven numbers allocated. The missing numbers are 1 and 3. But we can also see that there is already a 3 in row I (square If) so a 3 can not go in square Ic, the 3 is forced to be allocated in the other square Ac it is the only square in column c where a 3 can be allocated.

Whenever there are eight allocated in a group with only one remaining you can assign a symbol by applying the 'only choice' or 'only square' rule as they both have the same effect in this case.

One of the most useful solution strategies involves using the 'Only Square' rule. Other Sudoku authors refer to it as 'slicing and slotting'. It is a quick way of spotting squares to solve as it can be easily done in your head by scanning the puzzle grid. It almost always finds a square or two. At the heart of the technique is taking groups of three rows and columns in turn, working methodically through the whole grid. First look for all the 1s then all the 2s,3s etc. all the way through to 9. Here's an example of how it works.

Look at the top three rows at where the '1's are located - they are in row A column e (Ae) and Row C column a (Ca) There is no '1' in row B, but there must be one to allocate in one of the blank squares. Because of the 1 in Ae it can not go in any other of the squares in region Ad that is Bd;Be or Bf. By force of elimination there is only one place '1' can go in row B and that is in the highlighted square Bi. Using the same logic for the following three rows D;E;F there is once more two of them with a 1 in them squares Eh and Ff. There is therefore a 1 missing from row D and because of the 1 in Eh it can't be in Di, '1' must therefore be assigned to Dc. For the last three rows there are already three 1s Gd; Hb and Ig so there is no '1' left to allocate.

You can then look at the 2s in these three sets of three rows. In rows A;B;C there are 2 in Ai and Cb so there is a 2 missing in row B, but in this case there are 3 unallocated squares Bd;Be and Bf but it can't be quickly decided in which one should go the 2. The same happens in rows D;E;F there are two 2s but both Ed and Ef are possible. Finally in G;H;I there are two 2s Gg and Hc and this means there is a 2 missing in row I. The existing 2s mean there is only one place it can go - square Id. You continue this scan through all rows then all columns in groups of three and then through all the numbers 1 to 9.

So the general principle is to scan rows and columns in groups of three and look to see where if anywhere the number being scanned has been allocated. If you find two out of the three then you know that the missing number can only go in one of three squares in this row (or column), and often enough only one of these is possible and therefore the solution.

More rarely needed in Sudoku, but exceptionally useful is the sub-group exclusion rule. This takes quite a bit more explaining as instead of 'forcing' an allocation of a number to a square, it is an application of logic that 'excludes' possibilities that on first sight look possible. By excluding one possibility for a square may mean another possibility can then be assigned there as it was the only other alternative left for the square.

A sub-group is a term used here to describe a set of three squares that are the intersection between a Sudoku region and a row or column. Every row and column has three subgroups in the three regions it crosses. In this example the region Aa has been color coded to show the three subgroups it forms with columns a; b and c. The three pink squares are the sub-group intersecting region Aa and column a; the yellow squares with column b and the green ones with column c. The region also has three sub-groups with the Rows A; B and C. In fact every square in the grid belongs to two subgroups - one for the column it is in and one for the row it is in.

The Sudoku rule makes use of the fact that it's often possible to prove that a number must only occur somewhere in a sub-group and not elsewhere in a group but it can't be directly deduced which of the three sub-group squares it must occur in. In effect we have a partial allocation : the symbol must be in part of the region and not in the other squares. Having established allocation within a sub-group this knowledge can be applied to the rest of the region excluding the possibility of the same number occurring in those squares.

Here is a brief example using the simpler 4x4 grid. SudokuDragon has been used with possibilities enabled and exclusions switched on so that the grid directly shows the squares where the exclusion rule comes into play.

First look at column d, it's easy to see that the '1' must go in the square Cd and that's the only place it can go in the region Cc. Applying the subgroup rule for the subgroup shared between row d and region Cc (highlighted wuth blue) means that '1' can only occur in this subgroup and can not go in any other square in the region, in this case Cc or Dc, so that is why '1' is shown as excluded with a dark background by the SudokuDragon puzzle solver. Moreover because Dc could only take a '1' or '4' it's now certain that '4' must be allocated here.

The other subgroup we could have used in this Sudoku puzzle example is the one shared between column a and region Cb (highlighted in red). Here we can tell that '4' must be allocated in Ca as that is the only place in column a that can take it. So using the subgroup rule '4' can not go in Cb or Db, and so we can safely assign 1 to Db.

Note that these 4x4 Sudoku examples do not really show the full impact of the scheme as it's just not possible to have many options so the simpler rules could have been used to solve these squares more easily.

In this more complex 9x9 puzzle the action happens in the central region Dd. It is the subgroup of this region with the highlighted row F that is of interest. Look at the squares in row F that a 5 can go, it cant go in Fa (because of Aa) nor in Fh (because of Dh) nor in Fi (because of Bi). That only leaves Fd and Ff both of which occur as a shared sub-group with region Dd. The subgroup exclusion rule means that a 5 can not go in the remaining shared squares highlighted in purple : Ed or Ef.

Sudoku Dragon has highlighted quite a few possibilities in other squares that can be safely excluded using this same rule - for example the 8s in Ce and Cf and the 4s in Eg and Eh. This last example is particularly useful since square Eg is left with only one possibility with the 4 excluded, 7 must be allocated there.

More rarely you may find you need to use the twin (or triplet) exclusion rule in order to solve some of the more difficult Sudoku puzzles. It is the strategy to use when the other strategies have been applied and they don't give any more new solved Sudoku squares. In essence it is about spotting matching groups of possibilities in a group (row, column or region). Spotting these groups takes time and it is quite easy to make mistakes, so this is where you need pencil and paper (or the SudokuDragon puzzle solver).

In its simplest case there are two or more unallocated squares in a region and there are two numbers that can only go in the same two squares and no others. This does not help with allocating the numbers directly as the number could go in either square. However, if one of the two squares there is another possible number then this number can be discounted as it is excluded because of the presence of a twin elsewhere in the group. It all stems from the presence of a twin. An example is the best way to get your mind around this rule.

Look at this 4x4 grid. There are a number of easy squares that could be filled, but we'll ignore them as this is only to show the use of the twin rule. Look at the region Aa, none of the squares have yet been allocated. Both '2' and '3' must go somewhere in the region and there are only two squares that they can go. We have a twin in squares Aa and Ba. In square Aa a 1 was also flagged as possible this can now be safely excluded, also square Ba seems to allow a 4 but this is also excluded because of the twin. How does this work? There are only two ways that the twin of {2,3} can be allocated, either as '2' in Aa and the '3' in Ba or alternatively '3' in Aa and the '2' in Ba. This does not allow the possibility of the '1' being allocated in Aa or the '4' being allocated in Ba. Whenever there are a restricted number of possibilities restricted to the same number of squares this logic can be applied.

The rule for twins extends to triplets too. If we find that three symbols have only three shared possible squares in a group (row, column or region) then all other possibilities in these three squares can be discounted too. And on it goes, the same sort of rule applies to quadruplets, quintruplets etc. but these are very rarely found in real puzzles.

This rule is sometimes called the hidden twins rule as the twins are not immediately evident and discovering the twin is the challenge.

Similar but slightly different is the use of 'naked' twins to exclude other possibilities in the group. In this case the twins squares are evident on their own and are used to exclude possibilities in other squares in the same group.

The 4x4 grid has the region Ca highlighted. The 'naked twins' are located in Ca and Cb. Because these two squares have no other possibilities we know that a '2' must go in Ca and '3' in Cb or else '3' in Ca and '2' in Cb, no other valid possibility exists. So looking at Da the naked twin excludes '2' occurring here, this square must be allocated to '1'.

The twin, triplet, quadruplet rules are stated in terms of the size of the sub-group (2,3,4...) but a chain is also possible. A chain can take in any number of squares, for example if the first three squares in a group allow possibilities {1,7}; {4,7} and {1,7} we have a closed chain group of three symbols {1,4,7} this is not a twin or a triplet but the general permutation rule means that if we are clever enough to spot it then 1, 4 and 7 elsewhere in the group can be safely excluded as possibilities.

In looking for twins and general permutations we have restricted ourselves to look at possibilities within a single group at a time. The shared sub-group rule is an example of a rule where more than one intersecting group is used to determine possibilities. The X-Wing is similar to this in that it requires looking at multiple groups at once. A better name for this strategy might be 'box' as it requires four squares to form the four corners of the box. These squares must be the only permitted squares for that symbol in that row of one symbol (or column). This box arrangement now forms a two dimensional pairing. If the symbol spotted occurs in the top left of the box it must then also only occur in the bottom right square of the box, the only other alternative is if it occurs in the top right in which case it must occur in the bottom left square. No other option is possible for these squares and symbol. The usefulness of this rule that both the possible allocations put the symbol in the two columns (or rows) involved and so this knocks out possibilities anywhere else in the column (or row).

Here's an example (and it takes time to find a puzzle with an X-Wing in it). Sudoku Dragon has highlighted all the squares where a 4 is allocated or looks like it can be allocated. The rows C and G are crucial. They both have only two squares that can take a 4: Ca; Cf; Ga and Gf - highlighted in green - this is a vital precondition. Moreover the 4s form the corners of a rectangular box (highlighted in yellow). How is this useful? Well, because there must be a 4 in both column a (either in Ca or Ga) and also in column f (either in Cf or Gf), we can exclude all other possible 4s from these columns. So all the purple highlighted squares Aa; Ba; Bf; and Ha can have the option of a '4' discounted.

The term X-Wing is I believe from the name of Star War fighter which had an X shaped cross-section.

Believe it or not the Swordfish is yet another complication on top of the X-Wing, instead of four squares forming a linked cycle of possible allocations the Swordfish rule allows more linked pairs to form the group. In this case we have not just two pairs of two possibilities for 9 but three : in columns b; e and h. These squares are highlighted in orange. It's a box with an extension to it on one side : hence the term Swordfish. Because these three columns have these coinciding end squares the same rule applies. Any '9's that we find in rows that are part of the grid can be safely excluded because we know that a 9 must occur in one of the two orange squares in the row and so can't be located elsewhere. These excluded squares are highlighted in purple (Fc; Gf and Fg).

Of course, the Swordfish is not the end of the matter we can extend the logic to four interlinking pairs of possibilities and then five etc.. You'll feel a real sense of achievement if you locate a Swordfish and use it to help solve a puzzle!

When all else fails, there is one technique that is guaranteed to always work, indeed you could solve any Sudoku puzzle just using this strategy and no other. It's simply a matter of working through all the alternatives until it is solved. Because there are so many alternatives (billions) you won't want to use it too often. You start with a square and choose arbitrarily one number from the possibilities. You need to make a note of the choice you made though. Now continue solving squares until the puzzle is solved or it is un-solvable. A Sudoku puzzle becomes un-solvable because an incorrect allocation has been made. This shows up as two squares in the same region having the same number (breaking the rules) or as a square in a region unable to take any number at all (breaking the rules). If this happens you have to back-track all the allocations until you come back to the square you guessed, and then choose another alternative. Sudoku Dragon makes this easy because it supports 'Undo' - you don't need to remember all the squares you allocated. You can also add a note to indicate which squares were guessed so you can stop going back and undoing the allocations.

The reason that the Labyrinth is mentioned is that this is the strategy to get your way out of a Maze, you can always solve it as long as you run through all the alternatives in a consistent, logical fashion. If turning right leads to a dead end, retrace steps and try straight ahead, if that fails try left. In this was all possible alternatives are chosen.

Copyright © 2005 - 2008 Sudoku Dragon