Sudoku (1) P89454

Statement

Write a program that finds all the possible solutions of a sudoku.

Input

Input consists of 81 numbers between zero and nine, plus the bars and dashes that can be seen at the instances. The zeros indicate positions of unknown value. Except zeros, there will not be any repeated number in any row, nor any column, nor any of the nine squares $3 \times 3$ .

Output

Your program must print all the possible solutions of the given sudoku, in lexicographical order, and each one with a line in white in the end. It must print "-1" if there is not any possible solution.

Observation

The test data of this exercise are done in a way that a backtracking that simply fulls the rows from top to bottom and from left to right is fast enough.

Public test cases

Input

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

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

Input

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 0 0 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 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

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 9 8 7 | 2 3 1
7 8 9 | 2 3 1 | 4 6 5
---------------------
2 9 4 | 1 7 8 | 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

Input

1 2 3 | 4 5 6 | 7 8 9
9 8 7 | 3 2 1 | 6 5 4
4 5 6 | 7 8 9 | 1 2 3
---------------------
3 9 2 | 8 4 5 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0
---------------------
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0

Output

-1

Information

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