Algorytmy z nawrotami

(backtracking)

Algorytmy z nawrotami poznamy na przykładzie dwóch problemów „szachowych”: rozstawienia hetmanów i wędrówki skoczka po szachownicy.

Rozstawienie hetmanów

Problem polega na rozstawieniu n hetmanów na szachownicy n*n w taki sposób, by się nawzajem nie atakowały. Przypomnijmy, że hetman atakuje każde pole znajdujące się bądź w tym samym wierszu co on, bądź w tej samej kolumnie, bądź na jednej z dwóch przekątnych (patrz rysunek poniżej).

Jak łatwo sprawdzić, dla n=2 i 3, rozwiązania nie istnieją. Dla większych wartości n rozwiązania istnieją, co więcej, dla dużych n jest ich bardzo dużo. Chcemy napisać program, który dla zadanego n będzie znajdować którekolwiek z tych rozwiązań.

Algorytm naiwny mógłby polegać na sprawdzaniu wszystkich możliwych ustawień hetmanów. Ze względu olbrzymią liczbę tych ustawień efektywność tego algorytmu jest co najmniej wątpliwa. Istnieję algorytmy znacznie bardziej efektywne. Bazują one na regularności rozwiązań. Przyglądając się Rysunkowi 2 łatwo zauważyć, że w obydwu przedstawionych rozwiązaniach hetmany ustawione są wzdłuż dwóch linii. Łatwo się przekonać (do czego zachęcam czytelnika), że rozwiązania te dają się rozszerzyć na wiele innych wartości n, w szcególności na n nieparzyste.

Algorytm z nawrotami, który rozważymy, jest dość prostą modyfikacją algorytmu naiwnego. Przedstawiamy go, by zilustrować klasyczną technikę programowania.

Idea algorytmu.

Algorytm próbuje ustawiać hetmany w kolejnych kolumnach począwszy od pierwszej kolumny (oczywiście w każdej kolumnie ustawia tylko jednego hetmana). W każdej z kolumn szuka pierwszego pola (począwszy od dolnego), na którym postawienie hetmana nie koliduje z hetmanami z wcześniejszych kolumn. Jeśli takie pole istnieje, ustawia na nim hetmana i przechodzi do kolejnej kolumny. Jeśli nie istnieje - algorytm powraca do poprzedniej kolumny i próbuje przestawić hetmana na kolejne nie kolidujące pole. Może się zdarzyć, że algorytm będze musiał cofnąć się aż do pierwszej kolumny. Taka sytuacja pokazana jest na Rysunku 3.

Implementacja

Sprawdzanie czy pole jest atakowane

Jednym z problemów, które będziemy musieli rozwiązać, jest znalezienie metody sprawdzania, czy dane pole (powiedzmy pole <i, j>) szachownicy nie jest atakowane przez hetmany ustawione we wcześniejszych kolumnach. W tym celu musimy sprawdzić, czy żaden z tych hetmanów nie znajduje się:

• w i-tym wierszu (to jest łatwe);

• na tych samych przekątnych co pole <i, j>.

Jak łatwo zauważyć, pola dla których obydwa indeksy są sobie równe leżą na tej samej przekątnej, idącej od lewego górnego pola do prawego dolnego pola. Tuż nad nią leżą pola, których pierwszy indeks jest o jeden mniejszy od drugiego indeksu, a tuż pod nią - pola, których pierwszy indeks jest o jeden większy od drugiego indeksu. Te obserwacje skłaniają nas do uważniejszego przyjrzenia się róznicom i sumom indeksów pól. (patrz Rysunek 4).

Tak więc sprawdzenie, czy pole leży na tej samej przekątnej co pole <i,j>, sprowadza się porównania różnicy indeksów tego pola z wartością i-j oraz sumy jego indeksów z wartością i+j.

Pamiętanie rozstawienia hetmanów

Może się wydawać, że algorytm musi używać dwuwymiarowej tablicy [1..n,1..n] do pamiętania stanu wszyskich pól szachownicy. Zauważmy jednak, że wystarczy pamiętać pozycje hetmanów. Do tego celu użyjemy jednowymiarowej tablicy

w:array[1..n] of integer;

Element w[i] będzie równy j, jeśli w i-tej kolumnie hetman został ustawiony w j-tym wierszu. Przykładowo, dla rozstawienia hetmanów z Rysunku 3, tablica w przyjmie wartości:

Program

Komentarz do wybranych instrukcji:

• Procedura init

• w[1]:=1; - ustawienie hetmana z pierwszej kolumny na polu <1,1>

• for i:=2 to n do w[i]:=0; - ustawienie pozostałych hetmanów poza szachownicą.

• Funkcja wolne

• Funkcja jest typu boolean, a więc jej wartością może być false lub true.

• W pętli while sprawdzamy dla kolejnych i, począwszy od i=1, aż do i=x-1, czy hetman z i-tej kolumny nie atakuje pola <x,y>. Pętlę kończymy, jeśli natkniemy się na hetmana atakującego to pole, bądź też sprawdzimy wszystkie hetmany. O tym co było przyczyną zakończenia pętli mówi nam zmienna OK. Jeśli po zakończeniu pęti ma ona wartość false, to oznacza, że pole <x,y> jest atakowane, jeśli ma wartość true, to żaden z rozstawionych hetmanów nie atakuje tago pola.

• Do tego celu moglibyśmy także wykorzystać pętlę

for i:=1 to x-1 do.....

wówczas jednak nie moglibyśmy tak elegancko zakończyć pętli w przypadku, gdy już znajdziemy hetmana atakującego pole <x,y>. Do przerwania pętli for moglibyśmy użyć instrukcji break, jednak występuje ona nie we wszystkich wersjach Pascala.

• Funkcja ustawhetmany

• Zmienna k pamięta numer ustawianego hetmana. Zaczynamy od drugiego hetmana (tj. od hetmana z drugiej kolumny). Następnie w każdej iteracji pętli while albo uda się ustawić k-tego hetmana (wówczas zmienną k należy zwiększyć o 1) albo sztuka ta się nie uda (wówczas k należy zmniejszyć o 1).

• Teraz możemy docenić zalety nadania w procedurze init wartości zero elementom tablicy w. Dzięki temu możemy teraz w pętli while jednolicie potraktować sytuację, w której hetmana z k-tej kolumny wstawiamy dopiero na szachownicę i taką, w której hetman ten już stał, lecz musimy poprawić jego pozycję (tj. przesunąć na następne nie atakowane pole w tej kolumnie), ponieważ przy obecnym ustawieniu, niepowodzeniem zakończyły się próby ustawienia hetmanów w dalszych kolumnach. W obydwu przypadkach wystarczy wartość w[k] zwiększać o jeden. Realizowane jest to w pętli:

repeat

inc(w[k])

until (w[k]>n) or wolne(k,w[k]);

Kolejne instrukcje inc przesuwają hetmana po kolejnych polach k-tej kolumny tak długo, aż napotkamy nie atakowane pole bądź wyskoczymy hetmanem poza szachownicę. To, z którą sytuacją mamy do czynienia badane jest w instrukcji

if (w[k]<=n) then inc(k)

else begin w[k]:=0; dec(k) end

Jeśli w[k]<=n, to hetmana w k-tej kolumnie udało się ustawić, a więc należy przejść do następnej kolumny (inc(k)); w przeciwnym razie musimy cofnąć się do poprzedniej kolumny (dec(k)), a wartość w[k] należy ustawić na 0, co odpowiada temu, że k-ty hetman jest poza szachownicą.

Wędrówka skoczka po szachownicy

program konik;

const n=8; m=8;

type pole=record x,y:integer end;

var ruchy: array[1..8] of pole;

lr,kier:integer;

pk:pole;

sz:array[1..n,1..m] of integer;

hist:array[0..m*n] of pole;

procedure init;

var i,j:integer;

begin

ruchy[1].x:=2 ; ruchy[1].y:=1 ;

ruchy[2].x:=1 ; ruchy[2].y:=2 ;

ruchy[3].x:=-1 ; ruchy[3].y:=2 ;

ruchy[4].x:=-2 ; ruchy[4].y:=1 ;

ruchy[5].x:=-2 ; ruchy[5].y:=-1;

ruchy[6].x:=-1 ; ruchy[6].y:=-2;

ruchy[7].x:=1 ; ruchy[7].y:=-2;

ruchy[8].x:=2 ; ruchy[8].y:=-1;

for i:=1 to n do

for j:=1 to m do sz[i][j]:=0;

pk.x:=1; pk.y:=1;

lr:=1;

hist[1].x:=1; hist[1].y:=1;

end;

procedure cofnij;

begin

sz[pk.x,pk.y]:=0;

dec(lr);

pk.x:=hist[lr].x; pk.y:=hist[lr].y;

end;

procedure przesun(nr:integer);

begin

sz[pk.x,pk.y]:=nr;

inc(lr);

pk.x:=pk.x+ruchy[nr].x; pk.y:=pk.y+ruchy[nr].y;

hist[lr].x:=pk.x; hist[lr].y:=pk.y

end;

function okreslonyruch(skad:pole; kier:integer):boolean;

var nx,ny:integer;

begin

nx:=skad.x+ruchy[kier].x;

ny:=skad.y+ruchy[kier].y;

okreslonyruch:=(nx>=1) and (nx<=n) and (ny>=1) and (ny<=m)

end;

function nastruch(skad:pole):integer;

var kier:integer;

begin

kier:=sz[skad.x,skad.y];

repeat

inc(kier)

until (kier>8) or okreslonyruch(skad,kier) and

(sz[skad.x+ruchy[kier].x,skad.y+ruchy[kier].y]=0);

if kier>8 then nastruch:=0 else nastruch:=kier

end;

procedure pokazwynik;

var i,j:integer;

begin

writeln;

for i:=1 to n*m do writeln(hist[i].x:3, hist[i].y:3)

end;

begin

init;

while (lr>=1) and (lr<m*n) do

begin

kier:=nastruch(pk);

if kier=0 then cofnij else przesun(kier)

end;

if lr=0 then writeln('nie mozna skoczkiem obejsc szachownicy ',n,' x ',m)

else pokazwynik

end.

H

Rys.1. Kółkiem oznaczone są pola atakowane przez hetmana znajdującego się na polu z literą H

Rys.2. Przykładowe rozwiązania dla n=4 i n=5.

H

H

H

H

H

H

H

H

H

H

H

H

Rys.3. W pewnym momencie działania algorytm zachłanny dochodzi do sytuacji przedstawionej obok. Próba znalezienia niekolidującego pola w czwartej kolumnie zakończy się niepowodzeniem. Podonie zakończą się proby przestawienia hetmanów w 3-ciej, a następnie w 2-giej kolumnie. Skuteczne okaże się dopiero przestawienie hetmana w pierwszej kolumnie o jeden wiersz do góry.

i=

1

2

3

4

5

6

7

8

j= 1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

i-j= 7 6 5 4 3 2 1 0

i-j=

-7

-6

-5

-4

-3

-2

-1

i+j=

2

3

4

5

6

7

8

i+j= 9 10 11 12 13 14 15 16 0

Rys.4. Wszystkie pola leżące na tej samej przekątnej idącej z lewego górnego rogu do prawego dolnego rogu mają taką samą sumę indeksów (lewy rysunek). Natomiast pola leżące na tej samej przekątnej idącej z prawego górnego do lewego dolnego rogu maja taką samą różnicę indeksów (prawy rysunek).

1 4 2 0

w[i] :

i :

1 2 3 4

program hetmany;

const n=8;

var

w:array[1..n] of integer;

i:integer;

procedure init;

{początkowe ustawienie tablicy w}

var i:integer;

begin

w[1]:=1;

for i:=2 to n do w[i]:=0;

end;

function wolne(x,y:integer):boolean;

{sprawdzenie, czy pole <x,y> jest atakowane przez

hetmany ustawione w kolumnach 1,2,...,x-1}

var i:integer;

OK:boolean;

begin

OK:=true; i:=1;

while (i<x) and OK do

if (w[i]-i=y-x) or (w[i]+i=y+x) or (w[i]=y) then

OK:=false else inc(i);

wolne:=OK

end;

function ustawhetmany:integer;

{funkcja realizuje algorytm z nawrotami; jeśli uda się

ustawić n hetmanów, funkcja przyjmuje wartość n+1;

w przeciwnym razie przyjmuje wartość 0}

var k:integer;

begin

k:=2;

while (k<=n) and (k>=1) do

begin

repeat

inc(w[k])

until (w[k]>n) or wolne(k,w[k]);

if (w[k]<=n) then inc(k)

else begin w[k]:=0; dec(k) end;

end;

ustawhetmany:=k

end;

begin

init;

if ustawhetmany=n+1 then

begin

writeln;

for i:=1 to n do write(w[i]:3)

end else writeln('nie mozna rozstawic hetmanow');

end.

---