Zadanie 7 (termin oddania: 2 II 2006, godz. 23:59)

Łamigłówka o nazwie Sudoku ma postać diagramu o 9 wierszach i
9 kolumnach, w którym część pól wypełniono liczbami całkowitymi
od 1 do 9. Zadaniem rozwiązującego jest umieszczenie w pustych
polach liczb od 1 to 9 tak, by w każdym wierszu, w każdej
kolumnie i w każdym z 9 bloków 3 na 3 składajacych się na
diagram, każda z liczb od 1 do 9 wystapiła dokładnie raz.

W postaci tekstowej diagram będziemy reprezentowali przez 9
wierszy, każdy po 9 znaków. Znakami tymi będą cyfry z kolejnych,
wiersz po wierszu, pól diagramu oraz zera dla pól pustych. 

Napisz program, który wczyta z wejścia tekstową reprezentację
diagramu i sprawdzi, ile łamigłówka ma rozwiązań. Jeśli
rozwiązanie jest jedno, program powinien je wypisać stosując
ten sam format, co w wypadku danych wejściowych, czyli 9 wierszy
po 9 cyfr.

Jeśli łamigłówka nie ma rozwiązań lub jest więcej niż jedno
rozwiązanie, program powinien wypisać napis 'Liczba rozwiazan: ',
a po nim liczbę rozwiązań.

Np. dla danych:

870003000
004907056
000001070
000000035
600000002
430000000
010200000
360104500
000500081

program powinien wypisać:

876453219
124987356
953621874
791842635
685319742
432765198
519278463
368194527
247536981

a dla tych samych danych po zmianie pierwszego znaku pierwszego
wiersza na 0 program powinien wypisać:

Liczba rozwiazan: 50

Wskazówki:

Pole z wiersza w i kolumny k znajduje się w bloku o numerze
((w-1) div 3)*3+((k-1) div 3)+1.

W rozwiązaniu zastosuj technikę z nawrotami wypełniając puste
pola, na wszystkie możliwe sposoby, z zachowaniem warunków
poprawnosci, liczbami od 1 do 9.

Oprócz informacji o liczbach zapisanych w poszczególnych polach
diagramu warto też pamiętać, dla każdego wiersza, kolumny i bloku,
jakie liczby już się w nich znajdują. Dzięki temu łatwiej
sprawdzimy, jaką liczbę możemy wpisać w danym polu.