Problem description
Łamigłówka Sudoku polega na uzupełnieniu planszy 9 × 9 liczbami. W każdej komórce należy wpisać jedną z liczb ze zbioru {1, 2, …, 9}. Liczby umieszczone w każdym wierszu oraz w każdej kolumnie nie mogą się powtarzać. Dodatkowo, planszę dzielimy na dziewięć kwadratów 3 × 3 liniami po trzecim i szóstym wierszu oraz po trzeciej i szóstej kolumnie. W każdym takim kwadracie liczby również nie mogą się powtarzać.
Niektóre z liczb łamigłówki są już wpisane. Napisz program, który rozwiąże łamigłówkę Sudoku.
Wejście
Wejście składa się z dokładnie dziewięciu wierszy. W każdym z nich znajduje się dziewięć znaków. Każdy znak to cyfra od 1 do 9 włącznie lub znak kropki oznaczający, że dane pole planszy nie zostało jeszcze wypełnione.
Wyjście
Wyjście powinno się składać z dziewięciu wierszy jak na wejściu z kropkami zamienionymi na cyfry.
Możesz założyć, że testy są tak dobrane, że zawsze istnieje co najmniej jedno rozwiązanie. Jeżeli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.
Przykład
| Input | Output | |
|
|