What is Sudoku?
Sudoku, sometimes spelled Su Doku, is a logic-based placement puzzle, also known
as Number Place in the United States. The aim of the canonical puzzle is to
enter a numerical digit from 1 through 9 in each cell of a 9x9 grid made up of
3x3 subgrids (called "regions"), starting with various digits given in some
cells (the "givens"). Each row, column, and region must contain only one
instance of each numeral. Completing the puzzle requires patience and logical
ability. Although first published in 1979, Sudoku initially caught on in Japan
in 1986 and attained international popularity in 2005.
How To Play
You can navigate the grid using the arrow keys or clicking on the square using
the mouse. Clicking on a square will select it, shading the square. To enter a
number in the square, press a number key (from 1 to 9). To replace a number
that you have already entered, just press the correct number key (from 1 to 9).
To clear out a square, setting it to back to its original blank state, press
the delete key. You can navigate the grid using the arrow keys or clicking on
the square using the mouse.
Solving techniques
The strategy for solving a puzzle may be regarded as comprising a combination
of three processes: scanning, marking up, and analyzing. The top right region
must contain a 5. By hatching across and up from 5s elsewhere, the solver can
eliminate all the empty cells in the region which cannot contain a 5. This
leaves only one possibility (shaded).
Scanning
Scanning is performed at the outset and throughout the solution. Scans need to
be performed only once in between analyses. Scanning consists of two
techniques:
Cross-hatching: the scanning of rows to identify which line in a region may
contain a certain numeral by a process of elimination. The process is repeated
with the columns. For fastest results, the numerals are scanned in order of
their frequency, from high to low. It is important to perform this process
systematically, checking all of the digits 1–9. Counting 1–9 in regions, rows,
and columns to identify missing numerals. Counting based upon the last numeral
discovered may speed up the search. It also can be the case, particularly in
tougher puzzles, that the best way to ascertain the value of a cell is to count
in reverse—that is, by scanning the cell's region, row, and column for values
it cannot be, in order to see what remains. Advanced solvers look for
"contingencies" while scanning, narrowing a numeral's location within a row,
column, or region to two or three cells. When those cells lie within the same
row and region, they can be used for elimination during cross-hatching and
counting. Puzzles solved by scanning alone without requiring the detection of
contingencies are classified as "easy"; more difficult puzzles cannot be solved
by basic scanning alone.
A method for marking likely numerals in a single cell by the placing of pencil
dots. To reduce the number of dots used in each cell, the marking would only be
done after as many numbers as possible have been added to the puzzle by
scanning. Dots are erased as their corresponding numerals are eliminated as
candidates.
Marking up
Scanning stops when no further numerals can be discovered, making it necessary
to engage in logical analysis. One method to guide the analysis is to mark
candidate numerals in the blank cells. There are two popular notations:
subscripts and dots.
In the subscript notation the candidate numerals are written in subscript in
the cells. Because puzzles printed in a newspaper are too small to accommodate
more than a few subscript digits of normal handwriting, solvers may create a
larger copy of the puzzle. The second notation uses a pattern of dots in each
square, where the dot position indicates a number from 1 to 9. The dot notation
can be used on the original puzzle. Dexterity is required in placing the dots,
since misplaced dots or inadvertent marks inevitably lead to confusion and may
not be easily erased. An alternative technique is to "mark up" the numerals
that a cell cannot be. A cell will start empty and as more constraints become
known, it will slowly fill until only one mark is missing. Assuming no mistakes
are made and the marks can be overwritten with the value of a cell, there is no
longer a need for any erasures.
Analysis
The two main approaches to analysis are "candidate elimination" and "what-if".
In "candidate elimination", progress is made by successively eliminating
candidate numerals from cells to leave one choice. After each answer has been
achieved, another scan may be performed—usually checking to see the effect of
the contingencies. One method works by identifying "matched cells". If
precisely two cells within a scope (a particular row, column, or region)
contain the same two candidate numerals (p,q), or if precisely three cells
within a scope contain the same three candidate numerals (p,q,r), these cells
are said to be matched. The placement of these numerals anywhere else within
that same scope would make a solution impossible; thus, the candidate numerals
(p,q,r) scope can be deleted. When all else fails, ask the question, 'Would
entering the eliminated numeral prevent completion of the other necessary
placements?' If the answer to the question is 'Yes,' then the candidate numeral
in question can be eliminated.
In the "what-if" approach (also called "guess-and-check", "bifurcation",
"backtracking" and "Ariadne's thread"), a cell with two candidate numerals is
selected, and a guess is made. The steps are repeated unless a duplication is
found or a cell is left without a possible candidate, in which case the
alternative candidate must be the solution. For each cell's candidate, the
question is posed: 'will entering a particular numeral prevent completion of
the other placements of that numeral?' If the answer is 'yes', then that
candidate can be eliminated. The what-if approach requires a pencil and eraser
or a good layout memory.