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

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

  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ć:

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

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

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

%d bloggers like this: