Feladat: Adott nxn-es sakktáblán helyezzünk el 8 vezért úgy, hogy semelyik kettő sem üsse egymást.
Nem lehet: 2,3. Lehet: 1,4,5.
A megoldás módjai: valamely szisztéma szerint lépésről lépésre az összes lehetőséget kipróbáljuk (szisztematikus); vagy próbálgatással (heurisztikus).
Algoritmus (egy megoldás)
Procedure Probal(i: integer, var Q: boolean)
Var J: integer;
Begin
Repeat
J:=J+1;
If Y[J] and A[I+J] and B[I-J] then begin
X[I]:=J; Y[J]:=false;
A[I+J]:=false; B[I-J]:=false;
If (I < 8) then begin
Probal(I+1, Q);
If not Q then begin
Y[J]:=true;
A[I+J]:=true;
B[I-J]:=true;
End;
End;
Else Q:=true;
End;
Until Q or (J=8);
End;
Magyarázat
Q: ha találtunk megoldást, igazzá válik
I: a szintet tárolja, és megőrzi az értéket
J: lokális változó, az utolsó próbálkozás helyének sorát tárolja
Y,A,B,X: globális változók
J:=J+1: végigmegy az összes lehetséges soron, egészen J=8-ig
Y[J]: logikai változókat tartalmazó tömb
A[I+J]: mellékátlók (az indexek összege)
B[I-J]: főátlók (az indexek különbsége)
X[I]:=J: Letesszük az elemet. Így X tömb I-edik eleme J lesz. Az (I,J) pozícióba tettünk elemet
Y[J]:=false: megjegyzi, hogy a J-edik sor foglalt
A[I+J]:=false: megjegyzi, hogy a mellékátlókba már nem tehetünk elemet
B[I-J]:=false: megjegyzi, hogy a főátlókba már nem tehetünk elemet
If (i<8): Mivel még nem jutottunk el a 8. Oszlopba (csak ott találhatunk megoldást), nem vagyunk készen. Egy szinttel feljebb lépünk {probal(i+1,Q)} a globális keretekkel.
If not Q: ellenőrzi, hogyan léptünk vissza. Ha nincs megoldás, Q értéke hamis. Ha találtunk, akkor is visszalépünk, de Q értéke igaz lesz.
Y[J]:=true; A[I+J]:=true; B[I-J]:=true: Ha nem találtunk megoldást (Q értéke hamis), levesszük a tábláról a most felhelyezett elemeket, mivel ez az elrendezés nem ad megoldást. A sorok és átlók felszabadulnak.
Else Q:=true: Ha Q értéke igaz, elértünk a 8. oszlopba, megoldást találtunk.
Until Q or (J=8): Mivel Q igaz, befejeződik a repeat ciklus, és az eljárás is. Visszalép egészen az 1-es szintig, az eredmény pedig az X tömbben jelenik meg.
Ha Q hamis volt, a következő sorral próbálkozik, egészen 8-ig, s a ciklus emiatt áll le.
Megvalósítás
Y: array[1..8] of boolean;
A: array[2..16] of boolean;
B: array[-7..7] of boolean;
Mindegyiket for ciklusok segítségével kell igazra állítani. A Q kezdőértéke hamis.
Grafika: If Q then ’X tömb kirajzolása’
Algoritmus (összes megoldás)
Aránylag gyorsan megoldható az összes megoldása keresése.
Procedure probal(i: integer)
Var j: integer;
Begin
Ciklus k=1-től n-ig {k az adott szint, minden lehetőséget végigpróbál}
k-adik jelölt kiválasztása
ha megfelel, akkor jegyezzük fel
ha i<n akkor probal(i+1); {ha nem vagyunk kész, következő szint}
különben a megoldás kinyomtatása {ha elértük n-t}
feljegyzés törlése {mindenképp töröljük, ha találtunk megoldást, akkor is}
ciklus vége
end;
