Even more Sudokus P78955

Statement

thehtml

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.

Public test cases

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

Information

Author: Salvador Roura
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++