Transcript HKOI2006 Analysis and Solution Senior Q2 – Toggle

HKOI2006 Analysis and Solution
Junior Q3 – Sudoku
HKOI Training Team
2006-01-07
Statistics





Attempts: 42 (out of 69)
Mean: 46.91
Max: 100 (3)
Min: 0
Std Dev: 41.05
Statistics
12
10
8
6
4
2
0
0
20
40
60
80
100
The Problem


Given an incomplete Sudoku puzzle,
solve for the remaining cells
Only the center 9 cells are empty
Observation

For each test case, there is at most one
solution

Why?
Observations

For any cell in the center region, there
must be exactly one number that can
be filled in without any violation to the
rules


Why?
Let’s prove it by contradiction…
Observations

Suppose ‘1’ and ‘2’ can both be filled in the
center cell without violation to rules
Observations

Fill ‘1’ into the center cell
1
Observations

Why can ‘2’ be filled in the center cell?
1
Observations

Because it has not appeared in the center
row nor the center column
1
Observations

So ‘2’ must be filled in somewhere in the
center row, and also the column
1
Observations

‘2’ has to be appeared in one of the two Red
cells, and also one of the two yellow cells
1
Observations

Since all 4 colored cells are in the same
region, two ‘2’s must be in the same region
 Contradiction
1
Solutions


For each cell, find if these is exactly one
number to fill in
“No solution” if none or >1 is found
Alternative Solution

Exhaust all possible permutations of 1
to 9 to find in the cells, then check
whether the solution is valid

This solution looks stupid, but it works
since there are only 9! = 362880
permutations in total
Common Mistakes


Forgot to handle the “No solution” case
Assume there are no violations in the
numbers already filled in
Questions?