1531834464

<17.

> Techniki algorytmiczne - przybliżone i dokładne

postawić teraz pierwszego hetmana na polu a3 (rys. 7a). Na rysunkach 7b, 7c i 7d zilustrowano dostawianie kolejnego hetmana w następnych kolumnach - na ostatnim z nich jest pokazane końcowe ustawienie czterech nieatakujących się hetmanów.

Rysunek 6.

Próby uzupełnienia hetmana stojącego na polu a 4 (rys. a) do pełnego ustawienia 4 nieatakujących się hetmanów - niepowodzenie

Możemy podsumować to postępowanie formułując algorytm, jaki wykonywaliśmy.

Algorytm. Rozstawianie hetmanów

Ustal kolejność przeglądania kolumn szachownicy i wykonuj następujące ruchy (kroki), zaczynając od kolumny pierwszej.

Ruch do przodu. Gdy znajdujesz się w ustalonej kolumnie, wybierz w niej dla hetmana pierwsze nie rozpatrzone w tym wykonaniu Ruchu do przodu pole, które nie jest atakowane przez żadnego hetmana ustawionego w którejś z poprzednich kolumn.

1.    Jeśli istnieje takie pole, to ustaw na nim hetmana, a następnie:

1.1.    jeśli jest to ostatnia kolumna, to wypisz uzyskane ustawienie hetmanów, złożone z n hetmanów, gdzie n jest rozmiarem szachownicy, jeśli ma być znalezione tylko jedno rozstawienie hetmanów, to zakończ ten algorytm. Jeśli chcesz przekonać się, czy istnieją jeszcze inne rozstawienia, to wykonaj nawrót do poprzedniej kolumny i wykonaj dla niej Ruch do przodu;

1.2.    jeśli nie jest to ostatnia kolumna, to przejdź do następnej kolumny i wykonaj dla tej kolumny Ruch do przodu.

2.    Jeśli nie istnieje takie pole, to wykonaj nawrót do poprzedniej kolumny i przejdź do wykonania dla niej Ruchu do przodu.

Rysunki 6b i 6c są ilustracją nawrotu, czyli ruchu do tyłu podczas poszukiwania miejsca dla kolejnego hetmana. Będąc w drugiej kolumnie, najpierw zostało wykorzystane pole b2, ale okazało się, że nie ma wolnego pola w trzeciej kolumnie dla trzeciego hetmana, wróciliśmy więc do drugiej kolumny i ustawiliśmy hetmana na drugim wolnym polu w tej kolumnie, czyli na bl. Okazało się, że i tym razem, ale w czwartej kolumnie,

%

KAPITAŁ LUDZKI