Uznałam, że nie ma co udawać, że komputer rozwiązuje cokolwiek symulując człowieka i postanowiłam zaimplementować algorytm z nawrotami (backtracking). To, mam nadzieję, moja ostatnia próba rozwiązania sudoku z pomocą programowania.
Ogólna idea jest taka, żeby wybierać wartość i jeśli wartość jest ok posuwać się naprzód, aż do momentu kiedy stwierdzimy, że to nie była dobra wartość. Wtedy trzeba się wrócić i wybrać inną. I tak aż do momentu kiedy znajdziemy poprawne rozwiązanie.
Jak to mówią, zanim napisze się kod warto najpierw rozrysować sobie wszystko na kartce. Grunt żeby móc się rozczytać samemu 😀
Pierwsze próby rozpisania na sudoku 4×4. Można dostrzec próbę zidentyfikowania kroków potrzebnych o znalezienia rozwiązania: kiedy wstawiać wartość – kiedy resetować, kiedy wracać – kiedy przechodzić dalej
Na początek przyda się ustalenie kilku obiektów w klasie SudokuBacktracking. Przyda mi się tablica, będąca po prostu planszą. Wskaźniki na obecnie przetwarzaną kolumnę i rząd. Potrzebuję jeszcze czegoś gdzie mogę przechowywać liczby, które są już powstawiane na wejściu i nie powinny się zmienić. Będę je przechowywać w formie [„00”:true, „01”:false, …].
Na początek ustalenie jak powinny się zachowywać wskaźniki na kolumnę i rząd przy przechodzeniu do następnej i poprzedniej komórki.
Zaczynajmy zawsze z wizją końca – czas na metodę, która powie, czy sudoku jest już rozwiązane – czy wszystkie komórki mają wartość inną niż zero?
I teraz jak już wiadomo jak się przemieszczać i kiedy można zakończyć zabawę można przejść do najważniejszego: jak wygląda krok rozwiązania. Kiedy i co wsadzać w komórkę.
- Jeśli w komórce jest liczba, którą dostałam za darmo – idę do następnej komórki
- W przeciwnym wypadku pobieram wartość komórki do zmiennej. Zwiększam jej wartość o 1 i sprawdzam, czy nie jest większa od 9.
- Jeśli nie jest większa wrzucam ją do komórki i waliduję planszę – jeśli plansza jest prawidłowa – przesuwam wskaźnik na następną komórkę
- Jeśli jest większa od 9, resetuję to pole na planszy wpisując 0 i przesuwam się w tył do pierwszej komórki, która nie ma w sobie stałej wartości.
Tylko włożyć to w pętle while i można wyliczać:
Zwykłe wyjście na konsole nie jest jakoś bardzo imponujące:
Tak wygląda to w praktyce z użyciem biblioteki Processing:
Walidacja planszy to sprawdzanie, czy w każdym rekordzie, wierszu i kwadracie wszystkie liczby pojawiają się tylko raz (oczywiście z pominięciem 0)
I to by było na tyle. Cały kod na githubie