Sudoku Solving

I love doing Sudoku puzzles and have written programs for solving them. Over the years I have written solvers in VBA and C# using Excel forms, Windows forms, text output, etc.

Why visit the same problem more than once? Because I find it is a great way to try newly learned design patterns, technologies and/or ideas for algorithms. Since I already know how to solve the problem I can concentrate on the code I am writing and the techniques I am using.

But in this post I want to just record the methods I use to solve Sudoku puzzles.

I know a lot of people have posted the tips and tricks they use, but rarely do I see a complete set of simple AND advanced techniques. And never do I see the techniques expressed generically. Normally, you will find explanations that only cover the basic 9×9 Sudoku puzzle. It is hard to find anything tells you how to work through a 25×25 puzzle, or how to deal with 3×4 blocks (a puzzle with 12 possible values, not 9). Or what to do when the diagonals are supposed to have mutually exclusive values. And there are also puzzles where the blocks are not square or rectangular, but irregularly shaped – like a jigsaw puzzle.

So, I thought I would lay out the techniques I use, expressed from a programmer’s point of view and expressed generically so that they can be applied to ANY Sudoku puzzle.

Surprisingly, there are only 8 basic techniques that I have found, 2 of which are so basic for a human player that they are hardly worth mentioning (but they are critical when coding a programmatic solver). These 8 techniques cover many of the myriad tips and tricks I have seen out there. For instance, you can find websites that explain how to find hidden doubles, and hidden triples, and you may even find a site explaining hidden quads. But they are all the same technique, just the number of values, or rows or columns are different.

Additionally, some of the techniques, once expressed generically, have revealed new ways of working through the problems. A technique that deals with rows and columns can be applied to rows and blocks, or columns and blocks, if it is expressed generically.

So, here are my 8 techniques (or, as I refer to them “rules”) listed in ascending order of difficulty… but first, some quick terminology to make sure that we are all talking about the same things:

cell : A square in the puzzle. When the puzzle is completed, each cell will hold 1 symbol. Typical Sudoku puzzles have 81 cells.
symbol : One of the values that can be put into a cell. Typical Sudoku puzzles use 9 different symbols (1-9). Other puzzles may have 25 or more symbols.
assign : To indicate that a cell will hold 1 particular symbol to the exclusion of any other symbols.
row : A set of cells that share the same vertical coordinate. When the puzzle is completed, each cell in a row will be assigned a different symbol.
column : A set of cells that share the same horizontal coordinate. When the puzzle is completed, each cell in a column will be assigned a different symbol.
diagonal : A set of cells that share inversely related horizontal and vertical coordinates. Diagonals are only relevant to puzzles which are square in dimension. There are only 2 diagonals possible for a square Sudoku puzzle, and typical puzzles ignore them. When they are used and the puzzle is completed, each cell in a diagonal will be assigned a different symbol.
block : A set of adjacent cells of arbitrary arrangement. Typical Sudoku puzzles have 9 square blocks each containing 9 cells. More complex puzzles may have rectangular blocks or irregularly shaped blocks. When the puzzle is completed, each cell in a block will be assigned a different symbol.
group : A row, column, block or diagonal. When the puzzle is completed, each cell in the group will be assigned a different symbol.
cell’s groups : The set of groups that contain a particular cell. Each cell belongs to 1 row, 1 column, 1 block and may belong to 0, 1 or 2 diagonals.
possibilities : The set of symbols that remain as possible values that may be assigned to a cell. For each cell, this set changes as the puzzle is worked on until the cell is assigned a single symbol.

Sudoku-defs A Suduko defs-b

Rule 1

If a cell is assigned a symbol then the cell can have no other possibility.

This rule is illustrated in the next image, which shows that cell A6 has been assigned the symbol 7. Cell A6 has no other possibilities.

Rule 2

If cell x is assigned a symbol then no other cell in any of x’s groups can have that symbol as a possibility.

This rule is illustrated below. Since cell A6 has been assigned the symbol 7, that symbol has been removed as a possibility in all cells that are members of A6’s groups (outlined in blue).

(after applying rules 1 and 2)

Rule 3

If a cell has only one remaining possibility then the cell is assigned that possibility.

Rule 4

For a particular group, if a symbol can only exist as a possibility in one cell of the group, then assign that symbol to that cell.

This is often called a “hidden single”.

This rule is illustrated below. As cell H7 is the only cell in the block shown that has 4 as a possibility, the symbol 4 will be assigned to that cell.

Rule 5

For a particular group, g1, if a symbol can only exist as a possibility at the intersection of the group and one other intersecting group, g2, then the symbol cannot exist as a possibility in any other cells in the intersecting group g2.

e.g. in a regular 9×9 puzzle, if, in row 3 (g1), the possibility ‘2’ only occurs in the first block (g2), then ‘2’ does not occur in row 1 or row 2 of the first block.

This is sometimes called a “pointing pair”, “pointing triple”, etc.

(Rule 2 can be seen as a special case of Rule 5 where the number of cells where the symbol can be a possibility is 1)

Rule 6

If a set of n cells in a group consist of only possibilities from a set of n symbols, then no other cell in that group can have any of the possibilities from that set of symbols. (Derived from J. F. Crook’s paper at http://www.ams.org/notices/200904/tx090400460p.pdf)

This covers the rules called “naked pairs”, “naked triples”, etc.

(Rule 3 can be seen as a special case of Rule 6 where n is 1)

Rule 7

If, in a group, a set of n symbols exist as possibilities only in n cells, then the set of n cells cannot have possibilities that are not in the set of symbols.

This covers the rules referred to as “hidden pairs”, “hidden triples”, etc.

(Rule 4 can be seen as a special case of Rule 7 where n is 1)

Rule 8

If a symbol exists as a possibility only at the intersection of n groups (set A) and another set of n groups (set B) then the symbol cannot exist as a possibility for cells in set A or set B outside of the intersections.

e.g. If, in a standard 9×9 puzzle, for rows 4, 6 and 7 (set A n=3), the possibility of ‘2’ can only be placed in columns A, B and F (set B) – for instance A4, A7, B6, B7, F4 and F6, then ‘2’ cannot exist as a possibility in columns A, B and F for rows other than 4, 6 and 7. i.e. A5 can’t be ‘2’, F3 can’t be ‘2’, etc.

This covers the rules referred to as “X-Wing”, “Swordfish” and “Jellyfish”.

S	M	T	W	T	F	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Sudoku Solving

(after applying rules 1 and 2)

Like this:

Related

Leave a Reply Cancel reply