Transcript The Mathematics of Sudoku - National University of Singapore

The Mathematics of Sudoku
Helmer Aslaksen
Department of Mathematics
National University of Singapore
[email protected]
www.math.nus.edu.sg/aslaksen/
Sudoku grid
•
•
•
•
9 rows, 9 columns, 9 3x3 boxes and 81 cells
I will refer to rows, columns or boxes as units
(p,q) refers to row p and column q
I number the boxes left to right, top to bottom
Rules
• Fill in the digits 1 through 9 so that every
number appears exactly once in every unit
(row, column and box)
• Some numbers are given at the start to
ensure that there is a unique solution
History of Sudoku
• Retired architect Howard Garns of
Indianapolis invented a game called
“Number Place” in May 1979
• Introduced in Japan in April1984 under the
name of Sudoku (数独), meaning single
numbers
• Took the UK by storm in late 2004
Latin squares
• In 1783, Euler introduced Latin squares,
i.e., n x n arrays where 1 through n
appears once in every row and column
• A Sudoku grid is a 9x9 Latin square where
the 9 3x3 boxes contains 1 through 9 once
How many givens do we need to
guarantee a unique solution?
• This is an unknown mathematical problem
• There are examples of uniquely solvable
grids with 17 givens
(www.csse.uwa.edu.au/~gordon/sudokumi
n.php)
How many givens can we have
without guaranteeing a unique
solution?
2
9
4
5
8
1
3
7
6
8
7
1
6
3
9
2
5
4
3
6
5
7
4
2
1
8
9
6
5
3
4
2
8
7
9
1
7
4
9
1
6
3
8
2
5
1 9 4
3
7
9 3 8
7 1 5
5 4 6
6 5 9
4 6 1
3 7 2
5
1
6
2
9
7
4
3
8
How many Sudoku grids are there?
• It was shown in 2005 by Bertram
Felgenhauer and Frazer Jarvis to be
6,670,903,752,021,072,936,960
• This is roughly 0.00012% the number of
9×9 Latin squares
Why Sudoku is simpler than real
life
• If a number can only be in a certain cell,
then it must be in that cell
Elementary solution techniques
• We will first describe three easy
techniques
• Scanning (or slicing and dicing)
• Cross-hatching
• Filling gaps
Scanning
4
2
8
7
1
6
8
4
8
3
2
5
4
• We can place 2 in (3,2)
• You should start scanning in rows or
columns with many filled cells
• Scan for numbers that occur many times
Cross-hatching
Filling gaps
• Look out for boxes, rows or columns with
only one or two blanks
Intermediate techniques
• The elementary techniques will solve easy
puzzles
• I will discuss one intermediate technique,
box claims a row (column) for a number
Box claims a row (column) for a
number
4
2
8
7
2
1
6
8
4
8
3
2
5
4
• Box 1 claims row 1 for number 1
• We can place 1 in (3,8)
Box claims a row (column) for a
number
8
6
5
6
1
4
8
8
• Box 2 claims row 3 for number 8
• We can place 8 in (2,9)
• This is sometimes called “pointing
pairs/triples”
Advanced techniques
• For harder puzzles, we must pencil in candidate
lists
• This is called markup
Candidate Lists
Strategy
• If you believe the puzzle is easy, you
should be able to solve it using easy
techniques and it is a waste of time to
write down candidate lists
• If you believe the puzzle is hard, you
should not waste your time with too much
scanning, and go for candidate lists after
some quick scanning
Single-candidate cell
1
2
459
69
4589
7
4589
3
5
• 5 is the only candidate in (3,3)
• Called a naked single
Single-cell candidate
1
2
459
69
4589
7
4589
3
5
• (1,2) is the only square in which 6 is a
candidate
• Called a hidden single
Strategy
• Once you fill one cell, you must update all
the affected candidate lists
• Search systematically for naked or hidden
singles in all units
Naked pairs
• Cells 2 and 5 only contain 1 and 7
• Hence 1 and 7 cannot be anywhere else!
• We can remove 1 and 7 from the lists in all
the other cells
Hidden pair
145
69
35
357
348
156
9
2
578
478
135
7
• 6 and 9 only appear in cells 1 and 5
• Hence we can remove all other numbers
from those two cells, {6, 9} becomes a
naked pair and we get a hidden {1}
69
35
357
348
69
2
578
478
135
7
69
35
357
348
69
2
578
478
1
Naked triples
• Cells 2, 3 and 7 only contain a subset of
{3, 5, 6}
• Hence 3, 5 and 6 cannot be anywhere
else
• We can remove 3, 5 and 6 from the lists in
all the other cells
Naked triples
134
58
35
36
345
8
167
2
56
467
89
146
79
• Notice that none of the three cells need to
contain all three numbers
• {3, 5, 6} still forms a triple in cells 2, 3 and
7 even though all the three lists only
contain pairs
Naked and hidden n-tuples
• We can generalize the pairs and triples to
naked and hidden n-tuples
• If n cells can only contain the numbers
{a1,…, an}, then those numbers can be
removed from all other cells in the unit
• If the n numbers {a1,…, an} are only
contained in n cells in an unit, then all
other numbers can be removed from
those cells
Naked or hidden?
• Naked means that n cells only contain n
numbers
• Hidden means that n numbers are only
contained in n cells
• Naked removes the n numbers from other
cells
• Hidden removes other numbers from the n
cells
• Hidden becomes naked
Row (column) claims box for a
number
• In the middle row, 2 can only occur in the
last box
• Hence we can remove it from all the other
cells in the box
• Also called “box line reduction strategy”
Row (column) claims box for a
number vs. box claims row
(column) for a number
• Row claims box for a number means that if
all possible occurrences of x in row y are
in box z, then all possible occurrences of x
in box z are in row y
• Box claims row for a number means that if
all possible occurrences of x in box z are
in row y, then all possible occurrences of x
in row y are in box z
More advanced techniques
• X-Wing
• Swordfish
• XY-wing
X-Wing
• We can remove the 6's marked in the
small squares and we can place 9 in (7,9).
X-Wing Theory
• Suppose we know that x only occurs as a
candidate twice in two rows (columns),
and that those two occurrences are in the
same columns (rows)
• Then x cannot occur anywhere else in
those two columns (rows)
Swordfish
• This is just a triple X-wing
• Suppose we know that x occurs as a
candidate at most three times in three
rows (columns), and that those
occurrences are in the same columns
(rows)
• Then x cannot occur anywhere else in
those three columns (rows)
Swordfish 2
• We can place a 2 in (5,2)
Swordfish 3
• We don’t need nine candidate lists
XY-wing
• We can eliminate z from the cell with a “?”
• If there is an x in the top left cell, there has
to be a z in the top right cell
• If there is a y in the top left cell, there has
to be a z in the bottom left cell
XY-wing
• We don’t need a square; it is enough that
there are three cells of the form xy, xz and
yz, where the xy is in the same unit as xz
and the same unit yz
• We can eliminate z from the gray cells
below
What if you’re still stuck?
• Sometimes even these techniques don’t
work
• You may have to apply “proof by
contradiction”
• Choose one candidate in a list, and see
where that takes you
• If that allows you to solve the grid, you
have found a solution
Proof by contradiction
• If your assumption leads to a
contradiction, you can strike that number
off the candidate list in the cell
• Unfortunately, you may have to “branch” at
several cells
Solution by “logic”?
• Some people do not approve of proof by
contradiction, claiming that it is not logic
• It is obviously valid logic, but it is hard to
do with pen and paper
Where can I get help?
• There are many Sudoku solvers available
online
• Many of them allow you to step through
the solution, indicating which techniques
they are using
• http://www.scanraid.com/sudoku.htm
Warning!
• Sudoku is fun, but it is highly addictive
• Happy Sudoku!
Sample Puzzle
Sample Puzzle 2