The Math Behind Sudoku
Sudoku is a puzzle form that originated in puzzle books from the 1970's. It existed in relative obscurity until the early 2000's, when popular culture rediscovered it and it spread throughout the world as a worthy challenge for any self-confident puzzle solver. Since it requires little numerical math skills, instead relying on the juggling of set memberships, it can be approached by almost anyone. Also, sudoku puzzles span a wide spectrum of challenges, making it easy to start on easy forms and work into the most dificult types.
Sudoku uses 27 sets, each partially filled, to gives clues to one another for the completion of the board. The 27 sets are derived from:
- 9 rows of unique symbols (numbers 1..9)
- 9 columns of unique symbols (numbers 1..9)
- 9 regions of unique symbols (numbers 1..9)
Typically, when exploring a sudoku puzzle's cell for the only value which will
fit, one uses any of the 27 sets to remove choices. Tracking the possible values
in each cell is called "marking" and helps to quickly cross-reference the influences
from one set to another. Marking is used here to demonstrate how both entered values
and potential values can influence other cells.
Basic Rules [Cross Hatch Scanning]
First, one removes choices of symbols already present in the three obvious sets that each cell is a member of: row, column and region. As the start of the puzzle, few cells may yield a single valid entry from examining these other sets, but if a value can be entered, it cascades to enable a re-examination of the board. This is because each time a value is entered, it adds to the clues.
|
Using colors to identify the initial 3 sets of a sudoku cell's relationship
(cell with yellow circle) - it's Row, Column, Region. All cells belong to some row,
region or column, so the basic rules can be used to help fill in every cell.
Striped cells show how the row and column overlaps in the identified region. Take note though that every cell has 3 striped colors, because every row's cell coincides with a region and column. |
|
Using just the sets of Row, Region and Column, the yellow cell's possibilities
are reduced from {1..9} to just {4,5,7,8}.
This is because the other values {1,2,3,6,9} already exist in positions that are in the Row, Region or Column sets. |
Range Checking
Astute solvers quickly realize that more sets than the initial 3 will help provide clues for a single cell. Examining the row of the target cell, the other regions for this row (thus looking at the rows possibly above/below the taget's row) - one can gather further clues. This adds 2 region sets and 2 row sets to the clue-delivering sets: 4 total. Repeating this for columns, 4 more sets influence solving this single cell. Combined with the initial 3 sets, 11 sets (3 + 4 + 4) help provde a cell's value.
Subset Elimination
|
By using the far left region, one notices {4,5} must be placed in the two
empty cells - although one cannot determine which of the empty cells get
the 4 and 5.
This influences the yellow cell by removing the possibility of {4,5} there, since the 4 and 5 must be placed elsewhere in the row. Compounded with the initial scanning, only {7,8} are possible in the yellow cell. |
|
By using the lower right region, one notices {2,7} must be placed in the two
empty cells - although one cannot determine which of the empty cells get
the 2 and 7.
This influences the yellow cell by removing the possibility of {7} there, since the 7 must be placed elsewhere in the column. Compounded with the initial scanning, only {8} is possible in the yellow cell, enabling it to be filled confidently. |
This form of set influence has many forms, since it can appear horizontally or vertically. Most often, when a value can only appear in 1 row of a region, although its exact location is unknown, one can remove that possibility from adjacent cells in the row. This is because a value can only appear once in such a row, and the region demands it appear in one narrow area. Of course, this can be used for columns as well.
This still may not be enough to help solve a cell. Indeed, most of the difficult puzzles of sudoku reach a point where these 11 sets deliver no more definitive answers for open cells.
Grid Analysis
More to come...
Medusa 3D
More to come...
Almost-Locked Sets
More to come...