sudokist

Darius este pasionat de sudoku, dar din cauza profesorului lui de informatică, are prea multă temă și nu mai are timp să rezolve puzzle-uri. El vă cere ajutorul vostru pentru a-i face un program care rezolvă automat puzzle-urile.

Jocul de Sudoku se desfășoară pe o grilă de dimensiune $9 \times 9$, împărțită în $9$ sub-grile de dimensiune $3 \times 3$. La început, grila este parțial completată cu cifre de la $1$ la $9$. Celulele necompletate sunt marcate cu valoarea $0$.

Cerință

Să se scrie un program care primește un tablou de sudoku necompletat și afișează tabloul completat, astfel încât să fie respectate următoarele reguli simultan:

1. Fiecare linie trebuie să conțină toate cifrele de la $1$ la $9$ o singură dată.
2. Fiecare coloană trebuie să conțină toate cifrele de la $1$ la $9$ o singură dată.
3. Fiecare sub-grilă de $3 \times 3$ trebuie să conțină toate cifrele de la $1$ la $9$ o singură dată.

Date de intrare

Pe primele $9$ linii ale fișierului de intrare sudokist.in se găsesc câte $9$ numere naturale separate prin spații. Numerele sunt cuprinse între $0$ și $9$, unde $0$ reprezintă o celulă goală.

Date de ieșire

Pe primele $9$ linii ale fișierului de ieșire sudokist.out se vor găsi câte $9$ cifre separate prin spații, reprezentând grila de Sudoku completată corect. Dacă nu există nicio soluție validă, se va afișa valoarea $-1$.

Precizări

• Pentru exemple se acordă 5 puncte.

Exemplul 1

sudokist.in

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

sudokist.out

1 5 4 3 6 8 2 7 9 
3 8 9 1 2 7 5 6 4 
2 6 7 9 5 4 3 1 8 
9 3 5 4 7 1 8 2 6 
6 7 1 8 3 2 9 4 5 
8 4 2 6 9 5 1 3 7 
4 2 8 5 1 6 7 9 3 
5 1 3 7 4 9 6 8 2 
7 9 6 2 8 3 4 5 1 

Explicație

Pentru primul exemplu, se află rezolvarea corectă mai jos.

Configurația Inițială	Soluția Finală

Exemplul 2

sudokist.in

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

sudokist.out

-1

Explicație

Pentru al doilea exemplu, nu se poate completa prima căsuță, așa că se afișează -1.