Se citeste o grila Sudoku 9x9, partial completata (0 inseamna celula libera). Determinati, folosind metoda Backtracking, in cate moduri diferite poate fi completata grila astfel incat fiecare linie, fiecare coloana si fiecare careu 3x3 sa contina fiecare cifra de la 1 la 9 exact o data.
- Date de intrare
- Se citesc 9 linii, fiecare cu 9 valori (0-9), reprezentand grila initiala.
- Date de iesire
- Se afiseaza un singur numar: numarul de completari valide ale grilei.
- Restrictii
- Grila are 9x9 celule si are un numar mic de celule libere (deci un numar mic de completari posibile).
Exemple
Exemplul 1
Intrare
0 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
Iesire
1
Exemplul 2
Intrare
0 3 4 6 7 8 9 1 2 6 0 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
Iesire
1