Today we will share about the mathematics of Sudoku. I guess many of you have encountered with Sudoku before and attempted to solve it. However, how many of you have ever find out the mathematics behind this 9x9 grid of games? I guess not many of us did this. Well, no worry, let us introduce it to you all. We hope that after looking through this post, you all could understand Sudoku better!
First,
What is Sudoku ?
The diagram above is the Sudoku Grid.
The grid is the combination of 9 rows, 9 columns, 9 3x3 boxes and 81 cells.
We will now refer to rows, columns or boxes as units.
The notation (p,q) refers to row p and column q.
Throughout this post, we are going to number the boxes left to right, top to bottom.
Rules:
The rules of Sudoku is simple. We need to fill in the digits 1 through 9 so that every number appears exactly once in every unit (row, column and box).
Note that some numbers are given at the start to ensure that there is a unique solution.
Elementary solution techniques:
We will first describe three easy techniques:
1. Scanning (or slicing and dicing)
2. Cross-hatching
3. Filling gaps
From the diagram about, we can easily scan through and see that we can place "2" in (3,2).
Do you understand why is it so ?
Let's see. "2" has already appeared in the second and third box. Also note that "2" is located at the first and second row. Therefore, "2" has to be in first box third row. Since there is only one blank unit in first box third row, "2" must be in there.
In order to apply this strategy, you should start scanning in rows or columns with many filled cells or scan for numbers that occur many times.
2. Cross-hatching
This is another way of determining the location of a number.
From the diagram above, we can see that "5" is located at in first and second row and also the last column. By eliminating the impossible blank unit in the upper right box, there is only left with 1 possible unit to locate "5". Therefore, "5" must be in (3,7).
3. Filling gaps
Filling gaps here is simply means by looking out for boxes, rows or columns with only one or two blanks. Fill it up with the remaining number in the respective blank.
Intermediate solution techniques:
Box claims a row (column) for a number
From the diagram above, it is clear that since "1" appeared in second row, then "1" must be in box 1 row 1. We define this as Box 1 claims row 1 for number 1.
Hence, there is only 1 possibility of placing "1" in box 3, that is in (3,8).
Here is another example. Let's see if you can get this.
For this, we know that Box 2 claims row 3 for number 8. So, we can place 8 in (2,9).
This is sometimes called “pointing pairs/triples”
Advance solution techniques:
For harder puzzles, we must pencil in candidate lists. This is called markup.
The above diagram is called Candidate list.
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.
However, 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.
1. Single-candidate cell
Note that since "5" is the only candidate in (3,3), "5" must be in there.
This is called a naked single.
2. Single-cell candidate
Note that since (1,2) is the only square in which "6" is a candidate, "6" must be in there.
This is called a hidden single.
Strategy:
Once you fill one cell, you must update all the affected candidate lists. Then search systematically for naked or hidden singles in all units.
1. Naked pairs
Note that cells 2 and 5 only contain "1" and "7".
Hence "1" and "7" cannot be anywhere else!
Therefore, we can remove "1" and "7" from the lists in all the other cells
Then, fill in the naked single, we obtain:
2. Hidden pair
Note that "6" and "9" only appear in cells 1 and 5.
Hence we can remove all other numbers from those two cells.
Now, {6, 9} becomes a naked pair and we get a hidden {1}.
3. Naked triples
Note that 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.
Notice that none of the three cells need to contain all three numbers.
However {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
Note that 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.
This is 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.
***
Until here, I think most of you all should already get the basic solving technique of Sudoku. There are still more advance technique that we can apply. Do stay tuned if you are interested with this topic..=D
~Chow Cheng Li
