Even more Sudokus P78955
Write a program to find the unique solution of a Sudoku.
Input
Input begins with a number n, followed by n Sudokus. Every Sudoku consists of 81 numbers between zero and nine, plus the characters shown in the examples. A zero indicates an unknown value. Except for zeros, there are no repeated numbers in any row, nor in any column, nor in any of the nine squares 3 × 3. Every Sudoku has exactly one solution.
Output
For every Sudoku, print its unique solution, followed by an empty line.
Observation
A backtracking program that simply fills the rows from top to bottom and from left to right should not be fast enough to solve this exercise. Instead, at every step of the backtracking, fill the empty cell (or one of the empty cells) with less options left.
Input
2 0 8 0 | 0 5 9 | 0 0 0 7 0 3 | 0 0 0 | 0 0 0 6 4 9 | 7 0 0 | 0 0 0 ------+-------+------ 0 6 4 | 0 0 3 | 0 0 5 0 0 7 | 0 0 0 | 6 0 0 8 0 0 | 6 0 0 | 0 4 0 ------+-------+------ 0 0 0 | 0 0 7 | 3 2 8 0 0 0 | 0 0 0 | 1 0 7 0 0 0 | 8 9 0 | 0 0 0 1 2 3 | 4 5 6 | 7 8 9 4 5 6 | 0 7 0 | 0 0 0 7 8 9 | 0 0 0 | 0 6 0 ------+-------+------ 2 0 0 | 1 0 0 | 0 0 0 5 0 0 | 0 2 0 | 8 0 0 8 0 1 | 5 0 3 | 9 0 0 ------+-------+------ 3 0 0 | 0 6 0 | 1 9 8 6 0 0 | 0 0 0 | 0 2 7 9 7 5 | 8 0 0 | 0 0 3
Output
1 8 2 | 3 5 9 | 4 7 6 7 5 3 | 2 6 4 | 9 8 1 6 4 9 | 7 1 8 | 2 5 3 ------+-------+------ 2 6 4 | 9 7 3 | 8 1 5 9 1 7 | 4 8 5 | 6 3 2 8 3 5 | 6 2 1 | 7 4 9 ------+-------+------ 5 9 6 | 1 4 7 | 3 2 8 4 2 8 | 5 3 6 | 1 9 7 3 7 1 | 8 9 2 | 5 6 4 1 2 3 | 4 5 6 | 7 8 9 4 5 6 | 9 7 8 | 2 3 1 7 8 9 | 2 3 1 | 4 6 5 ------+-------+------ 2 9 4 | 1 8 7 | 3 5 6 5 3 7 | 6 2 9 | 8 1 4 8 6 1 | 5 4 3 | 9 7 2 ------+-------+------ 3 4 2 | 7 6 5 | 1 9 8 6 1 8 | 3 9 4 | 5 2 7 9 7 5 | 8 1 2 | 6 4 3
- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++