[groovy] Sudoku Backtracking – ostatnie starcie

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, …].

https://gist.github.com/jezinka/abe6b920e815c4a8f514b4783d0833fe

Na początek ustalenie jak powinny się zachowywać wskaźniki na kolumnę i rząd przy przechodzeniu do następnej i poprzedniej komórki.

https://gist.github.com/jezinka/98d1a220555dad4e237021d8bea23cc8

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?

https://gist.github.com/jezinka/06c6952b7b97ea43f111303a1a086ad2

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ę.

https://gist.github.com/jezinka/b17330bdf196d08fc2dd034ab82a4846
  1. Jeśli w komórce jest liczba, którą dostałam za darmo – idę do następnej komórki
  2. W przeciwnym wypadku pobieram wartość komórki do zmiennej. Zwiększam jej wartość o 1 i sprawdzam, czy nie jest większa od 9.
    1. 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ę
    2. 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ć:

https://gist.github.com/jezinka/0200e5f27283af7a15f115851433720b

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)

https://gist.github.com/jezinka/9857f8cf21c6d09076312065fd2ad580

I to by było na tyle. Cały kod na githubie

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.