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.