Sudoku, cunoscut si sub denumirea Locul Numarului, este un joc logic. Scopul jocului este de a plasa o cifra de la 1 la 9 in fiecare celula a unui caroiaj format de dimensiune 9×9, impartit 9 in regiuni de dimensiune 3×3, pornind de la o configuratie initiala, in care exista cifre plasate in anumite celule. In figura de mai jos este prezentat un exemplu (regiunile fiind delimitate de linii groase).

Fiecare linie, coloana si regiune trebuie sa contine o singura aparitie a fiecarei cifre. Completarea jocului necesita rabdare si logica. Desi pentru prima data a fost publicat in U. S. in 1979, Sudoku a avut succes pentru prima data in Japonia in 1986 si a obtinut popularitate internationala in 2005.

Cerinta

Scrieti un program care sa rezolve un joc Sudoku.

Date de intrare

Fisierul de intrare sudoku.in contine 9 linii, fiecare linie continand o succesiune de 9 cifre, reprezentand liniile de pe tabla de joc. Celulele goale sunt indicate prin cifra 0.

Date de iesire

Fisierul de iesire sudoku.out va contine 9 linii, fiecare linie continand 9 cifre nenule distincte, reprezentand solutia jocului. Cifrele scrise pe aceeasi linie nu vor fi separate prin spatii.

Restrictii

Fiecare joc din fisierele de test are o singura solutie.

Exemplu

Prof. DSc Stoyan Kapralov
Technical University - Gabrovo, Bulgaria
Contact: s.kapralov@gmail.com