Antal Alexandru (Courage) O grilă SUDOKU este o matrice 9 x 9 care respectă următoarele proprietăţi:
1. fiecare element al matricii este un număr natural între 1 şi 9;
2. fiecare linie conţine toate numerele naturale de la 1 la 9;
3. fiecare coloană conţine toate numerele naturale de la 1 la 9;
4. fiecare dintre cele 9 submatrici de dimensiune 3 x 3, evidenţiate prin linii îngroşate în exemplul de mai jos, conţine toate numerele de la 1 la 9.
Un puzzle SUDOKU este o matrice 9 x 9 completată parţial cu numere naturale de la 1 la 9. Mai jos este un exemplu de puzzle SUDOKU. O soluţie a unui astfel de puzzle este o grilă sudoku care coincide cu puzzle-ul pe poziţiile precompletate.
Cerința
Scrieţi un program care, pentru o matrice 9 x 9 dată, reprezentând un puzzle SUDOKU, determină o soluţie a unui astfel de puzzle, după regulile de mai sus.
Date de intrare
Fișierul de intrare sudoku.in conține o matrice 9 x 9 (câte 9 elemente pe câte o linie a fişierului, fiecare element fiind separat printr-un spaţiu), reprezentând un puzzle SUDOKU, în care poziţiile necompletate au valoarea 0.
Date de ieșire
Fișierul de ieșire sudoku.out va conține o matrice 9 x 9 (câte 9 elemente pe câte o linie a fişierului, fiecare element fiind separat printr-un spaţiu), reprezentând soluţia puzzle-ului din fişierul de intrare.
Restricții și precizări
- puzzle-ul din fişierul de intrare are soluţie unică, pentru toate testele
Exemplu:
sudoku.in
2 5 8 7 3 0 9 4 1 6 0 9 8 2 4 3 0 7 4 0 7 0 1 5 2 6 0 3 9 5 2 7 0 4 0 6 0 6 2 4 0 8 1 0 5 8 4 0 6 5 0 7 2 9 1 8 4 3 6 9 5 7 2 0 7 0 1 4 2 0 9 3 9 2 3 5 8 7 6 1 4
sudoku.out
2 5 8 7 3 6 9 4 1 6 1 9 8 2 4 3 5 7 4 3 7 9 1 5 2 6 8 3 9 5 2 7 1 4 8 6 7 6 2 4 9 8 1 3 5 8 4 1 6 5 3 7 2 9 1 8 4 3 6 9 5 7 2 5 7 6 1 4 2 8 9 3 9 2 3 5 8 7 6 1 4