Rozdział 8
Rekurencja
.
.
.
Przykład
W przykładzie przedstawimy znany szeroko w literaturze problem
znalezienia takiej drogi skoczka szachowego, aby każde pole szachow-
nicy było odwiedzone przez niego dokładnie raz.
Podobnie jak w poprzednim przykładzie do rozwiązanie tego proble-
mu wykorzystamy algorytm powrotu. Na wstępie określimy kolejność
wykonywania ruchów skoczkiem. W każdym etapie obiegania szacho-
wnicy próba wykonania ruchu będzie zgodna z tą kolejnością, która
może być dowolna pod warunkiem, że zawsze będzie taka sama. Przy-
jętą przez nas kolejność definiuje tablica przedstawiona na rys. 8.7.
Rys. 8.7. Kolejność wykonywania ruchów skoczkiem
Rozważmy teraz przykładową szachownicę o rozmiarach 4 * 4 i
położenie punktu początkowego 2,2. Spróbujmy wykonać kilka kroków
algorytmu powrotu. Kolejne ruchy wykonujemy zgodnie z przyjętą
kolejnością (zawsze zgodnie z ruchem wskazówek zegara poczynając od
ruchu zaznaczonego na rys. 8.7 cyfrą 1). W przypadku, gdy danego
posunięcia nie da się wykonać, próbujemy wykonać kolejny możliwy do
wykonania ruch z danego punktu. Poszczególne ruchy oznaczymy
kolejnymi liczbami całkowitymi (rys.8.8).
Rys. 8.8. Kilka ruchów skoczka na szachownicy
Zauważmy, że w sytuacji podanej na rys. 8.8 z punktu o współrzęd-
nych 4,1 nie można wykonać żadnego ruchu. Należy zatem wykonać
podstawowy krok algorytmu powrotu i cofnąć się do takiego położenia,
z którego można kontynuować ustawianie. W naszym przypadku
usuwamy ruch o numerze 4 i wykonujemy go teraz do punktu o współ-
rzędnych 2,1. Kilka następnych posunięć pokazuje szachownica przed-
stawiona na rys. 8.9.
| 1 |
|
14 |
5 |
2 |
| 2 |
4 |
1 |
8 |
11 |
| 3 |
13 |
10 |
3 |
6 |
| 4 |
|
7 |
12 |
9 |
| |
1 |
2 |
3 |
4 |
Rys. 8.9. Kilka ruchów skoczka na szachownicy po wykonaniu powro-
tu.
Dla ruchu o numerze 14 nie można wykonać żadnego następnego
posunięcia, musimy się zatem cofnąć do takiego położenia, z którego
można wykonać ruch dotychczas nie wykonywany. Analizując szachow-
nicę, dochodzimy do wniosku, że należy się cofnąć do ruchu o numerze
11 i ruch 12 zamiast do punktu o współrzędnych 4,3 wykonać do pun-
ktu o współrzędnych 1,2. Sytuację tę ilustruje rys. 8.10.
Przedstawiony algorytm zrealizujemy przy pomocy procedury reku-
rencyjnej. Unikamy w ten sposób jawnego pamiętania, który ruch
spośród ośmiu możliwych został wykonany. Na przykład w sytuacji
podanej na rys. 8.8 trzeba pamiętać dane:
numer ruchu startowego numer wykonanego ruchu
1 2
2 5
3 6
W przypadku konieczności powrotu do ruchu o numerze 3 będziemy
próbowali zrealizować posunięcie o numerze wyższym niż 6 spośród
ośmiu możliwych do wykonania ruchów. W tym przypadku zostanie
wykonany ruch o numerze 7.
| 1 |
|
12 |
5 |
2 |
| 2 |
4 |
1 |
8 |
11 |
| 3 |
|
10 |
3 |
6 |
| 4 |
|
7 |
|
9 |
| |
1 |
2 |
3 |
4 |
Rys. 8.10. Sytuacja na szachownicy po wykonaniu kolejnego powrotu.
Ogólna wersja algorytmu wykonywania następnego ruchu
wykorzystanego w procedurze o nazwie Ruch jest przedstawiona poni-
żej.
Algorytm 8.2
zdefiniuj ustawienie początkowe
repeat
begin
wybierz następny ruch
if ruch jest możliwy then
begin
zaznacz wykonanie ruchu
if są jeszcze wolne pola then
begin
wykonaj rekurencyjnie procedurę dla następnego ruchu
if ruch nie jest możliwy then
skasuj zapis ostatniego ruchu
end
end
end
until ruch został wykonany poprawnie lub nie ma więcej możliwych
ruchów
Podobnie jak przy ustawieniu ośmiu hetmanów na szachownicy
musimy teraz określić strukturę danych, która będzie dalej wykorzys-
tywana. Szachownicę będzie reprezentować tablica o nazwie szach.
Maksymalny rozmiar tej tablicy określimy w stałej nmax, natomiast
aktualny rozmiar tablicy będziemy wczytywać do zmiennej n. Kolejno
wykonywane posunięcia będą zapisywane w postaci liczb całkowitych.
Jeśli element (pole) tablicy ma wartość zero oznacza to, że pole to nie
było jeszcze odwiedzone. Parametry formalne procedury Ruch powinny
być następujące:
procedure Ruch(i,wsp1,wsp2: integer; var ok: boolean);
gdzie i oznacza numer ostatnio wykonanego ruchu, wsp1 oraz wsp2 są
współrzędnymi tego ruchu, zmienna ok określa czy udało się wykonać
ruch.
Możemy teraz przystąpić do precyzowania zdań występujących w
algorytmie 8.2. Zdanie
ruch jest możliwy
zapiszemy w postaci
if (wspnast1 in [1..n]) and (wspnast2 in [1..n]) then
if szach[wspnast1,wspnast2] = 0 then
gdzie wspnast1 oraz wspnast2 są współrzędnymi następnego ruchu.
Powyższe instrukcje sprawdzają, czy współrzędne leżą wewnątrz tabli-
cy i następnie czy pole o tych współrzędnych ma wartość zero, co ozna-
cza, że dane pole nie było odwiedzone. Instrukcji tych nie można połą-
czyć, ponieważ w przypadku gdy współrzędne nie leżą wewnątrz tabli-
cy, to zmienna szach[wspnast1,wspnast2] jest nieokreślona. Zdanie są
jeszcze wolne pola zapiszemy w postaci
i < n * n;
Oznacza to, że liczba wykonanych ruchów jest mniejsza niż liczba pól
szachownicy. Zdanie zaznacz wykonanie ruchu sprecyzujemy jako
szach[wspnast1,wspnast2] := i;
natomiast zdanie
skasuj zapis ostatniego ruchu
zapiszemy jako
szach[wspnast1,wspnast2] := 0;
Należy jeszcze wprowadzić zmienną lokalną o nazwie okwewn w
celu sprawdzenia, czy udało się wykonać następny ruch.
Na koniec zdefiniujemy sposób wyznaczenia współrzędnych wsp-
nast1 oraz wspnast2 w zależności od tego, który ruch spośród ośmiu
możliwych jest sprawdzany. W tym celu określimy globalną tablicę o
nazwie ruchy, zawierającą różnice współrzędnych dla każdego spośród
ośmiu ruchów. Tablica ta ma postać:
ruchy[1,1] := -2; ruchy[1,2] := 1;
ruchy[2,1] := -1; ruchy[2,2] := 2;
ruchy[3,1] := 1; ruchy[3,2] := 2;
ruchy[4,1] := 2; ruchy[4,2] := 1;
ruchy[5,1] := 2; ruchy[5,2] := -1;
ruchy[6,1] := 1; ruchy[6,2] := -2;
ruchy[7,1] := -1; ruchy[7,2] := -2;
ruchy[8,1] := -2; ruchy[8,2] := -1;
Na przykład aby wykonać piąty z kolei ruch dla skoczka stojącego
na polu o współrzędnych 2,3, należy zwiększyć współrzędną odpowiada-
jącą numerowi wiersza o 2 (ruchy[5,1]=2), a współrzędną odpowiadają-
cą numerowi kolumny zmniejszyć o jeden (ruchy[5,2]=-1), a zatem
musimy przestawić skoczka do pola o współrzędnych 4,2.
Program znajdowania drogi skoczka jest podany poniżej.
Program 8.4
program Skoczek;
{ Program znajdowania drogi skoczka na uogólnionej
szachownicy }
const
nmax = 20; { maksymalny rozmiar szachownicy }
var
i,j, { zmienne pomocnicze }
n, { rozmiar szachownicy }
pocz1,pocz2: { początkowe ustawienie skoczka }
integer;
ok: boolean; { zmienna kontrolna }
ruchy: array[1..8,1..2] of integer; { różnice
współrzędnych }
szach: array[1..nmax,1..nmax] of integer; {szachownica}
procedure Ruch(i,wsp1,wsp2: integer; var ok: boolean);
{ Rekurencyjna procedura wyznaczania następnego ruchu }
{ i - numer ruchu,
wsp1,wsp2 - aktualne współrzędne skoczka,
ok - zmienna kontrolna }
var
okwewn: boolean;
nr, { kolejny ruch spośród ośmiu możliwych ruchów }
wspnast1, wspnast2: { współrzędne następnego ruchu }
integer;
begin
nr := 0; { przygotowanie wyboru ruchów }
repeat
nr := nr + 1; { wybranie następnego ruchu spośród
ośmiu możliwych ruchów }
okwewn := false; { ustawienie wartości zmiennej
kontrolnej }
{ ustalenie współrzędnych następnego ruchu }
wspnast1 := wsp1 + ruchy[nr,1];
wspnast2 := wsp2 + ruchy[nr,2];
if (wspnast1 in [1..n]) and (wspnast2 in [1..n])
then
if szach[wspnast1,wspnast2] = 0 then { ruch
dopuszczalny }
begin
{ zaznaczenie ustawienia następnego ruchu }
szach[wspnast1,wspnast2] := i;
if i < n * n then { jeśli są wolne pola }
begin
{ rekurencyjne wywołanie procedury
dla następnego ruchu }
Ruch(i+1,wspnast1,wspnast2,okwewn);
if not okwewn then
{ usunięcie zaznaczenia ruchu }
szach[wspnast1,wspnast2] := 0
end
else
okwewn := true
end
until okwewn or (nr = 8); { aż ruch został wykonany
poprawnie lub nie ma więcej możliwych ruchów }
ok := okwewn { wyprowadzenie na zewnątrz wartości
kontrolnej }
end;
begin
writeln('Podaj rozmiar szachownicy');
readln(n);
writeln('Podaj punkty początkowe');
readln(pocz1,pocz2);
if ( not (n in [1..nmax])) or ( not (pocz1 in [1..n]))
or ( not (pocz2 in [1..n])) then
begin
writeln('Błąd danych');
halt
end;
{ wyznaczenie różnic współrzędnych }
ruchy[1,1] := -2; ruchy[1,2] := 1;
ruchy[2,1] := -1; ruchy[2,2] := 2;
ruchy[3,1] := 1; ruchy[3,2] := 2;
ruchy[4,1] := 2; ruchy[4,2] := 1;
ruchy[5,1] := 2; ruchy[5,2] := -1;
ruchy[6,1] := 1; ruchy[6,2] := -2;
ruchy[7,1] := -1; ruchy[7,2] := -2;
ruchy[8,1] := -2; ruchy[8,2] := -1;
{ przygotowanie tablicy }
for i := 1 to n do
for j := 1 to n do
szach[i,j] := 0;
szach[pocz1,pocz2] := 1;
Ruch(2,pocz1,pocz2,ok); { wyznaczanie ruchów }
if ok then
{ wydruk rozwiązania }
for i := 1 to n do
begin
for j := 1 to n do
write(szach[i,j]:4);
writeln
end
else
writeln('Brak rozwiązania')
end.
Na rys. 8.12 są podane wyniki wygenerowane przez program dla
szachownicy o rozmiarach 5 * 5, a na rys. 8.11 wygenerowane wyniki
dla rozmiarów 8 * 8. W obu przypadkach punktem startowym jest
punkt o współrzędnych 1,1.
| 8 |
1 |
38 |
55 |
34 |
3 |
36 |
19 |
22 |
| 7 |
54 |
47 |
2 |
37 |
20 |
23 |
4 |
17 |
| 6 |
39 |
56 |
33 |
46 |
35 |
18 |
21 |
10 |
| 5 |
48 |
53 |
40 |
57 |
24 |
11 |
16 |
5 |
| 4 |
59 |
32 |
45 |
52 |
41 |
26 |
9 |
12 |
| 3 |
44 |
49 |
58 |
25 |
62 |
15 |
6 |
27 |
| 2 |
31 |
60 |
51 |
42 |
29 |
8 |
13 |
64 |
| 1 |
50 |
43 |
30 |
61 |
14 |
63 |
28 |
7 |
| |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Rys. 8.11. Wygenerowane wyniki dla szachownicy o rozmiarach 8 * 8.
| 5 |
1 |
20 |
17 |
12 |
3 |
| 4 |
16 |
11 |
2 |
7 |
18 |
| 3 |
21 |
24 |
19 |
4 |
13 |
| 2 |
10 |
15 |
6 |
23 |
8 |
| 1 |
25 |
22 |
9 |
14 |
5 |
| |
1 |
2 |
3 |
4 |
5 |
Rys. 8.12. Wygenerowane wyniki dla szachownicy o rozmiarach 5 * 5.
.
.
.