The puzzle bank
A puzzle site releases fresh sudoku every morning, and before release the editor runs the new puzzles through a program: a solution must be found quickly, or checking a batch will take the whole day. The puzzles come from the real Sudoku Exchange bank, the same as in the article on backtracking: easy, medium, hard and diabolical mixed together, and among them are some on which a naive search writes tens of millions of digits.
A sudoku is a 9 × 9 grid divided into nine 3 × 3 boxes. Fill the empty cells with digits from 1 to 9 so that in every row, every column and every box all nine digits are different.
Input
The first line holds the number of puzzles T (1 ≤ T ≤ 200). Then T lines of 81 digits each: the grid read row by row from top to bottom, each row left to right; 0 marks an empty cell. Each puzzle has exactly one solution. Grids without empty cells occur too.
Output
For each puzzle, on a separate line, the solved grid in the same format, 81 digits without zeros.
Examples
Example 1
2 902006053180000020000970008700104300006000500008203007800037000030000071270600904 000000230037000090050940700000500049020080070540007000009052080070000460082000000
942816753187345629563972418729154386316798542458263197891437265634529871275681934 894175236137268594256943718763521849921384675548697123619452387375819462482736951
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Backtracking is fine here: place a digit, check the row, column and box, and erase it on a contradiction. But in what order should the empty cells be visited? Try visiting them in reading order on the seventh test and count how many digits the program writes.
2Hint 2
If some cell allows only one digit, there is nothing to think about with that cell. And if it allows none, the current branch is already dead, and it is better to learn this now than twenty levels down.
3The idea
Always fill the cell with the fewest allowed digits. Forced moves are made without branching, and a contradiction is discovered at the depth where it arose, not after a long search of everything below.
4Walkthrough
Masks. For each row, column and box keep a nine-bit mask of occupied digits: digit d is the bit 1 << d. The digits allowed in a cell are ALL & ~(row | col | box), and their number is the count of one bits. Placing a digit is three “or” operations, erasing it three “exclusive or”s.
Choosing a cell. The empty cells lie in a list; the first k are already filled. At step k look through the rest, find the cell with the fewest options and swap it with the k-th. If a cell with one option is found, there is no need to look further; one with zero options means the branch is dead, and we go back.
Why this is faster. The seventh test is made of the puzzles on which the in-order search was the longest in the whole bank of 893,916: up to 36.5 million digits written for one puzzle. Choosing the most constrained cell solves each of them in a few hundred digits. It is not a guarantee: the bank has a puzzle that costs it almost 18 thousand digits, but even that is thousands of times less than the worst cases of the in-order search.
4+Solution
5Complexity
In the worst case the search is exponential, and no fast algorithm is known for sudoku of arbitrary size: the problem is NP-complete. On a 9 × 9 grid with the most constrained cell the median over the bank is 97 digits written per puzzle, and the work for each is a look through at most 81 cells. Two hundred puzzles take fractions of a second even in Python.
6Common mistakes
- Visiting in order. A correct solution, and fast on most puzzles, but on the seventh test it writes tens of millions of digits and does not fit in the time.
- Checking “at the end”. Filling all cells and only then checking the grid is 950 options and more. You have to check after every digit.
- A forgotten restore. If, when erasing a digit, you do not remove it from the masks of its row, column and box, the search starts treating cells as occupied and loses the solution.
- A grid without empty cells. The second test starts with a completely filled grid: the solution is the grid itself.