Sudoku (1) P89454

Statement

thehtml

Feu un programa que trobi totes les solucions possibles d’un sudoku.

Entrada

L’entrada consisteix en 81 nombres entre zero i nou, més les barres i guions que es poden veure als exemples. Els zeros marquen posicions de valor desconegut. Excepte per als zeros, no hi haurà cap número repetit a cap fila, ni a cap columna, ni a cap dels nou quadres 3 × 3.

Sortida

Escriviu totes les solucions possibles del sudoku donat, en ordre lexicogràfic, i cadascuna amb una línia en blanc a continuació. Escriviu "-1" si no hi ha cap solució possible.

Observació

Els jocs de proves d’aquest exercici estan fets de manera que un backtracking que simplement ompli les files de dalt a baix i d’esquerra a dreta sigui suficientment ràpid.

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++