Sudoku P76807
Sudoku is a phenomenon all over the world. This addictive logic game, originated in the U.K. and popularized in Japan, has spread across the globe. The puzzles are now syndicated daily in newspapers in Australia, Germany, Scandinavia, …even Mireia is addicted to it!
The rules are easy: You are given a 9× 9 grid with some numbers in it, and you should fill in the grid so that every row, every column and every 3×3 box contains the numbers from 1 to 9. For instance, the puzzle on the left has as unique solution the grid on the right:
[linewidth=1.25pt](0,0)(9,0) (0,1)(9,1) (0,2)(9,2) [linewidth=1.25pt](0,3)(9,3) (0,4)(9,4) (0,5)(9,5) [linewidth=1.25pt](0,6)(9,6) (0,7)(9,7) (0,8)(9,8) [linewidth=1.25pt](0,9)(9,9)
[c](0.5,0.5)4 [c](2.5,0.5)5 [c](3.5,0.5)6
[c](1.5,1.5)2 [c](2.5,1.5)9 [c](3.5,1.5)1
[c](4.5,2.5)7 [c](5.5,2.5)5 [c](8.5,2.5)8
[c](2.5,3.5)6 [c](3.5,3.5)4 [c](4.5,3.5)2
[c](1.5,4.5)4 [c](2.5,4.5)8 [c](6.5,4.5)5 [c](7.5,4.5)6
[c](4.5,5.5)6 [c](5.5,5.5)1 [c](6.5,5.5)8
[c](0.5,6.5)1 [c](3.5,6.5)9 [c](4.5,6.5)3
[c](5.5,7.5)6 [c](6.5,7.5)4 [c](7.5,7.5)5
[c](5.5,8.5)2 [c](6.5,8.5)3 [c](8.5,8.5)7
(9,9) [linewidth=1.25pt](0,0)(0,9) (1,0)(1,9) (2,0)(2,9) [linewidth=1.25pt](3,0)(3,9) (4,0)(4,9) (5,0)(5,9) [linewidth=1.25pt](6,0)(6,9) (7,0)(7,9) (8,0)(8,9) [linewidth=1.25pt](9,0)(9,9)
[linewidth=1.25pt](0,0)(9,0) (0,1)(9,1) (0,2)(9,2) [linewidth=1.25pt](0,3)(9,3) (0,4)(9,4) (0,5)(9,5) [linewidth=1.25pt](0,6)(9,6) (0,7)(9,7) (0,8)(9,8) [linewidth=1.25pt](0,9)(9,9)
[c](0.5,0.5)4 [c](1.5,0.5)7 [c](2.5,0.5)5 [c](3.5,0.5)6 [c](4.5,0.5)8 [c](5.5,0.5)9 [c](6.5,0.5)1 [c](7.5,0.5)3 [c](8.5,0.5)2
[c](0,1) [c](0.5,0.5)8 [c](1.5,0.5)2 [c](2.5,0.5)9 [c](3.5,0.5)1 [c](4.5,0.5)4 [c](5.5,0.5)3 [c](6.5,0.5)6 [c](7.5,0.5)7 [c](8.5,0.5)5
[c](0,2) [c](0.5,0.5)6 [c](1.5,0.5)3 [c](2.5,0.5)1 [c](3.5,0.5)2 [c](4.5,0.5)7 [c](5.5,0.5)5 [c](6.5,0.5)9 [c](7.5,0.5)4 [c](8.5,0.5)8
[c](0,3) [c](0.5,0.5)5 [c](1.5,0.5)1 [c](2.5,0.5)6 [c](3.5,0.5)4 [c](4.5,0.5)2 [c](5.5,0.5)8 [c](6.5,0.5)7 [c](7.5,0.5)9 [c](8.5,0.5)3
[c](0,4) [c](0.5,0.5)2 [c](1.5,0.5)4 [c](2.5,0.5)8 [c](3.5,0.5)3 [c](4.5,0.5)9 [c](5.5,0.5)7 [c](6.5,0.5)5 [c](7.5,0.5)6 [c](8.5,0.5)1
[c](0,5) [c](0.5,0.5)7 [c](1.5,0.5)9 [c](2.5,0.5)3 [c](3.5,0.5)5 [c](4.5,0.5)6 [c](5.5,0.5)1 [c](6.5,0.5)8 [c](7.5,0.5)2 [c](8.5,0.5)4
[c](0,6) [c](0.5,0.5)1 [c](1.5,0.5)5 [c](2.5,0.5)7 [c](3.5,0.5)9 [c](4.5,0.5)3 [c](5.5,0.5)4 [c](6.5,0.5)2 [c](7.5,0.5)8 [c](8.5,0.5)6
[c](0,7) [c](0.5,0.5)3 [c](1.5,0.5)8 [c](2.5,0.5)2 [c](3.5,0.5)7 [c](4.5,0.5)1 [c](5.5,0.5)6 [c](6.5,0.5)4 [c](7.5,0.5)5 [c](8.5,0.5)9
[c](0,8) [c](0.5,0.5)9 [c](1.5,0.5)6 [c](2.5,0.5)4 [c](3.5,0.5)8 [c](4.5,0.5)5 [c](5.5,0.5)2 [c](6.5,0.5)3 [c](7.5,0.5)1 [c](8.5,0.5)7
Write a program to solve Sudoku puzzles. Your program will be tested against Sudokus that have appeared in some newspapers. These are guaranteed to have a unique solution.
Input
Input begins with a line with a number n ≥ 1. Follow n Sudokus, each one consisting of nine lines, each one with nine space-separated characters, which are digits from 1 to 9 and dots. The latter indicate cells that are still empty. There is a blank line before every puzzle.
Output
Print the solutions using the same format as in the input: First, print n on a line. For each puzzle, print nine lines, each with nine digits separated by spaces. Print a blank line before every solution.
Input
2 . . . . . 2 3 . 7 . . . . . 6 4 5 . 1 . . 9 3 . . . . . . . . 6 1 8 . . . 4 8 . . . 5 6 . . . 6 4 2 . . . . . . . . 7 5 . . 8 . 2 9 1 . . . . . 4 . 5 6 . . . . . 7 . . . . 2 . . 4 1 . . . . . 7 6 . 2 . . . 8 . 3 . 9 . . . 6 5 . 8 2 . . . . . 2 . . . . . 2 6 . 9 1 . . . 8 . 7 . 1 . . . 5 . 5 9 . . . . . 3 3 . . 5 . . . . 8
Output
2 9 6 4 8 5 2 3 1 7 3 8 2 7 1 6 4 5 9 1 5 7 9 3 4 2 8 6 7 9 3 5 6 1 8 2 4 2 4 8 3 9 7 5 6 1 5 1 6 4 2 8 7 9 3 6 3 1 2 7 5 9 4 8 8 2 9 1 4 3 6 7 5 4 7 5 6 8 9 1 3 2 7 3 5 9 6 2 1 8 4 1 9 8 4 3 5 7 6 2 2 6 4 1 8 7 3 5 9 9 7 3 6 5 4 8 2 1 5 8 1 7 2 3 9 4 6 4 2 6 8 9 1 5 3 7 8 4 7 3 1 6 2 9 5 6 5 9 2 7 8 4 1 3 3 1 2 5 4 9 6 7 8
- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Python