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.
- Ariadne's thread
- is a fancy name for trial and error: original reference. (See also bifurcation and guessing)
- Bifurcation
- is a widespread name for trial and error, whose origin is unknown. (See also Ariadne's thread and guessing)
- 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
- is an inaccurate term for trial and error. (See also Ariadne's thread and bifurcation)
- 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.