1531834465

<18>

Informatyka +

zabrakło nieatakowanego miejsca dla hetmana. W tej sytuacji, można powiedzieć, że dla ustawienia hetmana w pierwszej kolumnie na polu a4, w drugiej kolumnie sprawdziliśmy wszystkie możliwe ustawienia drugiego hetmana. Wykonujemy więc nawrót do pierwszej kolumny i ustawiamy hetmana na następnym możliwym polu, czyli na a3. jak pokazuję ilustracje na rys. 7, ta pozycja hetmana w pierwszej kolumnie może być uzupełniona do pełnego rozmieszczenia 4 hetmanów..

Rysunek 7.

Próby uzupełnienia hetmana, stojącego na polu a3, do pełnego rozmieszczenia hetmanów, zakończone sukcesem

Zilustrowany algorytm, po znalezieniu pełnego rozstawienia hetmanów (rys. 7d), można kontynuować (patrz krok l.l), aby się przekonać, czy nie ma jeszcze innego ustawienia czterech nieatakujących się hetmanów.

Ćwiczenie 23. Kontynuuj przerwany algorytm, by znaleźć jeszcze inne rozstawienia czterech nieatakujących się hetmanów na szachownicy 4x4. Znajdziesz jeszcze jedno pełne rozstawienie, a więc jest ich dwa. jaka jest między nimi zależność?

Ćwiczenie 24. Uzasadnij, w jaki sposób można otrzymać to drugie rozwiązanie (otrzymane w ćwicz. 23) bez uruchamiania dalszego przebiegu algorytmu poszukiwania z nawrotami, jakie jeszcze inne przekształcenia planszy szachownicy, a wraz z nimi - końcowego ustawienia hetmanów, mogą dać nowe ustawienia?

Przebieg poszukiwania z nawrotami przedstawia się zwykle w postaci drzewa poszukiwań. Dla naszego przykładu szachownicy 4x4 takie drzewo jest przedstawione na rys. 8. Poziomy w tym drzewie odpowiadają kolumnom (na pierwszym poziomie mamy pola a*, na drugim - pola b*, na trzecim - pola c* i na czwartym - d*), a wierzchołki - stawianym hetmanom (na rysunku podaliśmy w wierzchołkach pozycje hetmanów na planszy). Zauważ symetrię w tym drzewie względem pionowej osi - odpowiada ona symetrii planszy, którą zapewne wykorzystałeś w rozwiązaniach ćwiczeń 23 i 24.

%

KAPITAŁ LUDZKI

O*