# Sudoku (2) P95872

Statement

html

This exercise has the same wording than the exercise : “”: 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 × 3.

Output

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

Observations

• A backtracking that simply fulls the rows from top to bottom and from left to right will not be fast enough to solve this exercise.
• ### Information about the checker

You can print the solutions to this exercise in any order.

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

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

Output

```-1
```
• Information
Author