Przechadzka po szachownicy

Zadanie:
Odwiedź wszystkie pola szachownicy ruchem skoczka szachowego, odwiedzając każde pole tylko raz, zaczynając z a) rogu, b) jednego z pól środkowych, c) jednego z pól na brzegu, ale nie rogu.

Rozwiązanie:
Osoba (czyli Klient) sterująca skończkiem, zaczynającym z odpowiedniego miejsca zachownicy (czyli Odwiedzający), wykonuje ruchy skoczkiem po polach szachownicy (czyli Struktura Obiektów). W zależności od pola na których się znajdzie (czyli Elemencie Strukury) może wykonać zaakceptowane kroki – wycofać ruch (brak możliwości ruchu dalej, a są pola jeszcze bez odwiedzin), przejść do kolejnego wolnego pola, zakończyć przejście (wszystkie pola zostały odwiedzone). Próbowałem kiedyś to zadanie rozwiązać, zaczynając z różnych miejscach. Później spotkałem się z algorytmem dla programistów, który pozwala na określenie automatyczne takiej ścieżki.

Wzorzec Odwiedzający

Zaznaczone poprzez pogrubienie fragmenty odnoszą się do wzorca projektowego Odwiedzający (ang. Visitor). Przejście po Strukturze odbywa się tak, że najpierw następuje wysłane żądanie do Elementu Struktury z prośbą o akceptację Odwiedzającego. Następuje weryfikacja stanu. W momencie akceptacji, następuje polecenie odwiedzenia Elementu i wykonanie odpowiedniej operacji/polecenia.

Wzorzec jest przydatny, gdy chcemy przejść odpowiednią strukturę i wykonać dla każdego z elementów odpowiednią operację. W powyższym przykładzie obok zmiany stanu następuje wykonanie operacji wyboru kolejnego elementu, przejścia dalej lub wycofania, ponieważ stan wskazuje, że nie dane odwiedziny nie pozwolą na dalsze przejście. W takich sytuacjach zmiana operacji do wykonania powinna się odbywać bez wpływu na wszystkie elementy struktury. Załóżmy, że rozszerzamy strukturę o jeden poziom – np. szachownicę o jeden wiersz na dole, wtedy każdy z elementów struktury, na który ma ta zmiana wpływ, zostanie zmodyfikowany, a pozostałe nie ulegną zmianie.

Jedna uwaga do wpisu “Przechadzka po szachownicy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s