Sudoku

Pradinių duomenų failas:

sudoku.in  

Rezultatų failas:

sudoku.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Parašykite programą, sprendžiančią Sudoku galvosūkį.

Pradiniai duomenys

Pradinių duomenų faile įrašytas 81 skaičius, po 9 kiekvienoje eilutėje – tai duotas Sudoku galvosūkis. Tušti langeliai žymimi skaičiumi 0.

Rezultatai

Išspręstą Sudoku galvosūkį jūsų programa turi įrašyti į rezultatų failą, tokiu pat formatu, kaip pateikti pradiniai duomenys. Jei yra keli sprendiniai, programa gali pateikti bet kurį. Bent vienas sprendinys visada egzistuos.

Pavyzdys

1 0 4 2 6 7 5 8 9
5 0 6 1 0 9 0 2 0
0 9 2 0 4 3 6 1 7
7 1 9 3 2 4 0 6 5
4 6 3 8 7 0 0 9 1
2 8 5 9 1 6 3 0 4
3 4 0 6 9 8 7 5 2
6 2 0 4 0 0 9 3 8
0 0 8 7 3 0 1 4 0

1 3 4 2 6 7 5 8 9
5 7 6 1 8 9 4 2 3
8 9 2 5 4 3 6 1 7
7 1 9 3 2 4 8 6 5
4 6 3 8 7 5 2 9 1
2 8 5 9 1 6 3 7 4
3 4 1 6 9 8 7 5 2
6 2 7 4 5 1 9 3 8
9 5 8 7 3 2 1 4 6