## Su Doku

Su Doku is usually played on a 9 by 9 board, divided into 3 by 3 cells. You can generalize this into playing on an M×M square board broken into non-overlapping rectangular cells, each containing M squares (an obvious question is to how define a puzzle where M is a prime number). The solution of the puzzle is to place M symbols on the board such that each row, column or cell contains each symbol exactly once, without moving the initial clues. Puzzles with M<9 are called Sub Dokus, those for M>9 are called Super Dokus.

Technorati tag:

Related topic: Kakuro

# Names

## The mathematics of Su Doku

### Basic names

The puzzle below appeared in The London Times on Oct 6, 2005 and is copyrighted (if you object to this non-commercial use of this image, London Times, let me know). I use it here to illustrate some definitions which we will use in these pages. The grid
is the setting of this puzzle. It consists of the 81 boxes which are laid out in a 9×9 grid (what else!).
The squares
are the boxes are the places into which the numbers go; there are 81 of these squares in this grid.
The rows
are 9 squares lined up side by side. We count them from the top. The first row in this puzzle contains a 6, a 1 and an 8.
The columns
are 9 squares lined up one below the other. We count them from the left. The first column in this puzzle contains a 6, a 7 and a 1.
The blocks
are 9 squares, three rows of three each, which are grouped by thick lines in the puzzle shown.
The clues
are the numbers which are filled in to begin with. There are 36 clues in the example shown here.
The one rule
Fill in the grid with numbers from 1 to 9 such that each number occurs exactly once in each row, column and cell without changing the clues.

### Alphabetic list of all terms

Definitions are tricky: you want to encompass a complicated concept in one sentence, or at most a short para. If these definitions fail to illuminate, try to read through the pages on Shi Doku and Two Doku; most of these terms are explained there in context.

is a fancy name for trial and error: original reference. (See also bifurcation and guessing)
Bifurcation
Blocks
are groups of squares (neither rows nor columns) which are constrained by the one rule. An M×M grid contains M cells; each cell has M squares. If M is not a prime number, then a cell is a rectangle (or, if possible, a square). If M is a prime number then a cell is a polyomino
Cells
see blocks.
Clues
are the numbers which are filled into the grid to begin with. These are not to be changed in the course of completing the puzzle. (See also independent clues)
Columns
are the squares lined up one below the other. We count them from left to right. An M×M grid contains M columns; each column has M squares.
Depth first enumeration
is a systematic method for exploring all possibilties in a branching tree od decisions. In the context of Su Doku, whenever one has more than one possibility at a square, one explores each possibility one by one. This is closely related to "trial and error", but there one stops as soon as one reaches an acceptable possibility. In this case one enumerates all possiblities. (A fancy coinage for this is the garden of forking paths).
Garden of forking paths
is a fancy name for depth-first enumeration.
Geometric Su Doku group
is the set of all symmetries of the empty grid.
Givens
is another name for clues.
Go Doku
is the name for the puzzle on a 5×5 grid. It is an example of a Sub Doku and a Prime Su Doku.
Grid
is the setting of the puzzle. An M×M grid contains M2 squares to be filled in.
Guessing
Hints
is another name for clues.
Inconsistent puzzles
are those which have no solution which satisfies all the clues and the One Rule.
Independent clues
are the set of clues in a puzzle which cannot be deduced from each other. Given one set of clues there may be more than one way to pare away some to leave only independent clues.
Irreducible puzzles
are proper puzzles which no longer remain proper if any clue is removed.
Little group of a solution
is that subset of the Su Doku group which leaves a solution unchanged.
Maximum Su Doku
are irreducible puzzles which have the maximum number of clues.
Minimum Su Doku
are irreducible puzzles which have the minimum number of clues.
One rule
is the only rule of M×M Su Doku: "Fill in the grid with numbers from 1 to M such that each number occurs exactly once in each row, column and cell without changing the clues".
Orbit of a solution
is the set of all solutions obtained by the application of the Su Doku group to one solution.
Proper puzzles
are those which have exactly one solution which satisfies all the clues and the One Rule.
Puzzle forest
is the set of all reduction graphs, one for each essentially different solution.
Puzzle tree
See reduction graph.
Reduction graph
is the directed graph which has a complete solution at the root and all proper puzzles with this as the solution as nodes. Arrows point from each puzzle to every other obtained from it by removal of one clue. The irreducible puzzles are leaf nodes on this graph, ie, nodes with no arrows leaving them.
Roku Doku
is the name for the puzzle on a 6×6 grid. It is an example of a Sub Doku.
Rows
are the squares lined up side by side. We count them from the top down. An M×M grid contains M rows; each row has M squares.
Satisfactory puzzles
are those which require no trial and error in solving.
Shi Doku
is the name for the puzzle on a 4×4 grid. It is an example of a Sub Doku.
Skeleton of a puzzle
is obtained by writing a zero wherever there is a clue and one wherever the grid is blank. With an ordering of squares in the grid, the sequence of zeroes and ones becomes ordered, and hence can be treated as the binary representation of a number called the value of a skeleton.
Squares
are the places which have to be filled in. An M×M grid contains M2 squares.
Su Doku
usually means the puzzle on a 9×9 grid. In these web pages it is the generic term embracing all Sub Dokus and Super Dokus.
Su Doku group
is the full set of symmetries of Su Doku. It is the direct product of the geometric Su Doku group and the permutation group of the symbols.
Sub Doku
means the puzzle on an M×M grid where M<9. These include M=4, called Shi Doku, M=5, called Go Doku, and M=6, called Roku Doku.
Super Doku
means the puzzle on an M×M grid where M>9.
Trial and error
is a systematic method for finding the solution to a puzzle, involving assuming a value at one square, and proceeding until a contradiction is found, another assumption is needed, or the puzzle is solved. If a contradiction is found, then one goes back and changes the assumed value. Under the name depth-first search, it is known to computer science as a general technique for finding the solution of any problem which has finite (but possibly very large) number of outcomes. If done unsystematically, it resembles guessing. (Also called Ariadne's thread and bifurcation).
Value of a skeleton
See skeleton of a puzzle.

© Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 09 October, 2005. Last updated on 11 March, 2006.