The Mathematics of Sudoku

The Mathematics of Sudoku : The Mathematics of Sudoku Helmer Aslaksen Department of Mathematics National University of Singapore aslaksen@math.nus.edu.sg www.math.nus.edu.sg/aslaksen/

Sudoku grid : Sudoku grid 9 rows, 9 columns, 9 3x3 boxes and 81 cells I will refer to rows, columns or boxes as areas (p,q) refers to row p and column q I number the boxes left to right, top to bottom

Rules : Rules Fill in the digits 1 through 9 so that every number appears exactly once in every area (row, column and box) Some numbers are given at the start to ensure that there is a unique solution

History of Sudoku : 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 : 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? : 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/sudokumin.php)

How many givens can we have without guaranteeing a unique solution? : How many givens can we have without guaranteeing a unique solution?

Elementary solution techniques : Elementary solution techniques We will first describe three easy techniques Scanning (or slicing and dicing) Cross-hatching Filling gaps

Scanning : Scanning 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 : Cross-hatching

Filling gaps : Filling gaps Look out for boxes, rows or columns with only one or two blanks

Intermediate techniques : 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 : Box claims a row (column) for a number Box 1 claims row 1 for 1 We can place 1 in (3,8)

Box claims a row (column) for a number : Box claims a row (column) for a number Box 2 claims row 3 for 8 We can place 8 in (2,9) This is sometimes called “pointing pairs/triples”

Advanced techniques : Advanced techniques For harder puzzles, we must pencil in candidate lists This is called markup

Candidate Lists : Candidate Lists

Strategy : 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 : Single-candidate cell 5 is the only candidate in (3,3) Called a naked single

Single-cell candidate : Single-cell candidate (1,2) is the only square in which 6 is a candidate Called a hidden single

Strategy : Strategy Once you fill one cell, you must update all the affected candidate lists Search systematically for naked or hidden singles in all areas

Naked pairs : 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 : Hidden pair 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}

Naked triples : 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 : Naked triples 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 : Naked and hidden n-tuples We can generalize the pairs and triples to naked and hidden n-tuples If n candidate lists in an area only contain {a1,…, an}, then those numbers can be removed from all other lists in the area If {a1,…, an} are only contained in n candidate lists in an area, then all other numbers can be removed from those lists

Naked or hidden? : 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 : 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 (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 : More advanced techniques X-Wing Swordfish XY-wing

X-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 : 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 : 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 : Swordfish 2 We can place a 2 in (5,2)

Swordfish 3 : Swordfish 3 We don’t need nine candidate lists

XY-wing : 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 : 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 area as xz and the same area yz We can eliminate z from the gray cells below

What if you’re still stuck? : 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 : 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”? : 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? : 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! : Warning! Sudoku is fun, but it is highly addictive Happy Sudoku!

Sample Puzzle : Sample Puzzle

Sample Puzzle 2 : Sample Puzzle 2