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

Lamiglowka o nazwie Sudoku ma postac diagramu o 9 wierszach i
9 kolumnach, w ktorym czesc pol wypelniono liczbami calkowitymi
od 1 do 9. Zadaniem rozwiazujacego jest umieszczenie w pustych
polach liczb od 1 to 9 tak, by w kazdym wierszu, w kazdej
kolumnie i w kazdym z 9 blokow 3 na 3 skladajacych sie na
diagram, kazda z liczb od 1 do 9 wystapila dokladnie raz.

W postaci tekstowej diagram bedziemy reprezentowali przez 9
wierszy, kazdy po 9 znakow. Znakami tymi beda cyfry z kolejnych,
wiersz po wierszu, pol diagramu oraz zera dla pol pustych. 

Napisz program, ktory wczyta z wejscia tekstowa reprezentacje
diagramu i sprawdzi, ile lamiglowka ma rozwiazan. Jesli
rozwiazanie jest jedno, program powinien je wypisac stosujac
ten sam format, co w wypadku danych wejsciowych, czyli 9 wierszy
po 9 cyfr.

Jesli lamiglowka nie ma rozwiazan lub jest wiecej niz jedno
rozwiazanie, program powinien wypisac napis 'Liczba rozwiazan: ',
a po nim liczbe rozwiazan.

Np. dla danych:

870003000
004907056
000001070
000000035
600000002
430000000
010200000
360104500
000500081

program powinien wypisac:

876453219
124987356
953621874
791842635
685319742
432765198
519278463
368194527
247536981

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

Liczba rozwiazan: 50

Wskazowki:

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

W rozwiazaniu zastosuj technike z nawrotami wypelniajac puste
pola, na wszystkie mozliwe sposoby, z zachowaniem warunkow
poprawnosci, liczbami od 1 do 9.

Oprocz informacji o liczbach zapisanych w poszczegolnych polach
diagramu warto tez pamietac, dla kazdego wiersza, kolumny i bloku,
jakie liczby juz sie w nich znajduja. Dzieki temu latwiej
sprawdzimy, jaka liczba mozemy wpisac w danym polu.