7 Backtracking
   

• a bactracking lényege

• néhány backtrackinggel megoldható feladat
• nyolc vezér probléma
• útvonal megkeresése a labirintusban

        
     7.1 A backtracking technika lényege

     A programozásban a backtracking technika alatt a megoldástér szisztematikus bejárását értjük.

     A megoldás keresésekor elindulunk egy irányba, feltételezve, hogy az a jó irány. Ha valahol "zsákutcába" jutottunk, akkor visszalépegetünk addig a legközelebbi pontig, ahol tudunk más utat is választani és itt a rákövetkező (másik) úton megyünk tovább. A megvalósítás technikája általában rekurzió.
      

     Nyolc vezér probléma:
     Helyezzünk el egy 8x8-as sakktáblán 8 vezért úgy, hogy azok ne üssék egymást! (Tehát helyezzük el a vezéreket úgy, hogy se egy sorban, se egy oszlopban, se átlósan ne legyen egy vonalban kettő.) Hányféleképpen lehetséges így elhelyezni a vezéreket?

     Labirintus:
     Adva van egy M*N-es labirintus, (1,1) a bejárat, (M,N) a kijárat. Keressünk egy utat a bejárattól a kijáratig.

     Sakk-huszár:
     Keressünk egy olyan huszárugrás-sorozatot, amely minden egyes pontot érint a sakktáblán pontosan egyszer, és ugyan oda tér vissza, ahonnan indult.

     
     7.3 Nyolc vezér probléma

     A feladatunk tehát a következő: helyezzünk el egy 8x8-as sakktáblán 8 vezért úgy, hogy azok ne üssék egymást (tehát helyezzük el a vezéreket úgy, hogy se egy sorban, se egy oszlopban, se átlósan ne legyen egy vonalban kettő)! Általánosítva a feladatot: helyezzünk el egy NxN-es sakktáblán N vezért úgy, hogy azok ne üssék egymást!

     Az egyszerűség kedvéért mi most a 4x4-es sakktáblán fogjuk szemlélteni a megoldás megtalálásának a menetét.

     Az biztos, hogy minden oszlopban csak egy vezért helyezhetünk el, mivel egyébként a két vezér ütné egymást. Ezért megpróbáljuk mindegyik oszlopoban egymás után elhelyezni a vezéreket:

• Az első vezért letesszük az első oszlop első sorába.
• Majd a második oszlopba megpróbáljuk elhelyezni a vezért az első sortól haladva a negyedik sorig úgy, hogy az ne üsse az első oszlopban levő vezért. Ha sikerült, megyünk tovább a harmadik oszlopba; ha nem sikerült, akkor visszamegyünk az első oszlophoz és ott a vezért eggyel lejjebb tesszük.
• Így haladunk tovább, amíg nem sikerül a negyedik oszlopba is lerakni a vezért.

1. Az első oszlopban letesszük az első helyre (1. sorba) a vezért, feltételezve, hogy ez a jó hely:
          
   
        
   Majd megpróbáljuk a következő vezért lerakni a második oszlopba...
      
   
2. A második oszlop 1. és 2. sorába nem tehetünk vezért, mivel akkor ütné a már fent levőt (ábrán pirossal jelölve). A 3. sorba le lehet rakni a vezért, ezért letesszük oda, feltételezve hogy ez is a jó helyre került:
        
   
        
   Majd megpróbáljuk a következő vezért lerakni a harmadik oszlopba...
        
3. A harmadik oszlopban sem az 1., 2., 3., sem a 4. helyre nem tehetünk vezért, mivel mindegyik helyen ütné valamelyik már eddig fent levő vezért:
        
   
        
   Mivel így a harmadik oszlopba nem tudunk vezért tenni, ezért visszalépünk a második oszlopba és ott a vezért eggyel lejjebb tesszük (tehát a következő még nem kipróbált helyre):
        
   
      
   Ezek után ismét megpróbáljuk lerani a vezért a harmadik oszlopba...
        
4. Most a harmadik oszlopban az 1. sorba nem tehetünk vezért (mivel ütné az első oszlopban levőt), de a 2. sorba már tehetünk, ezért kitesszük oda:
      
   
      
   Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba...
         
5. A negyedik oszlopban nem tudunk az 1., 2., 3., de a 4. helyre sem tenni vezért, mivel ütné valamelyik már fent levőt:
      
   
      
   Ezért visszalépünk a harmadik oszlopba és megpróbáljuk ott máshová (a sorra következő helyekre, tehát a 3., 4. sorba) tenni a vezért. Azonban itt sem tehetjük a vezért sem a 3., sem a 4. sorba, mivel akkor ütné az első két oszlopban levőket:
      
   
      
   Ezért visszamegyünk a második oszlopba. Mivel itt már kipróbáltuk mind a négy helyet, ezért semmi mást nem tehetünk, mint hogy visszamegyünk egészen az első oszlopba és ott tesszük a vezért eggyel lejjebb:
      
   
        
   Majd megpróbáljuk a következő vezért ismét lerakni a második oszlopba...
         
6. Most a második oszlop 1., 2., 3. sorába nem rakhatjuk le a vezért, mivel akkor ütné az első oszlopban levőt. A 4. sorba azonban lerakhatjuk:
        
   
        
   Majd megpróbáljuk a harmadik vezért lerakni a harmadik oszlopba...
       
7. A harmadik oszlop 1. sorába letehetünk vezért, ezért lerakjuk oda:
        
   
        
   Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba...
        
8. A negyedik oszlop 1., 2. sorába nem tehetünk vezért, de a 3. sorba lerakhatjuk:
        
   
      
   Mivel sikerült a negyedik oszlopban is leraknunk a vezért, ezért megtaláltuk a feladat egyik megoldását, így befejeződhet az algoritmus. :-)
   

     
     7.4 Útvonal megkeresése a labirintusban

     Írjunk egy programot, amely backtracking segítségével megkeresi az útvonalat a bejárattól a kijáratig az alábbi labirintusban:
    
     
   
     Mielőtt nekiállnánk, gondoljuk át, hogy milyen adatszerkezet segítségével tudnánk ezt a labirintust ábrázolni a számítógépben. Jó megoldás lehet egy kétdimenziós tömb használata, mely a következő képpen nézne ki:
     
     
     
     A mi esetünkben egy 10x10-es tömböt használnánk, melyben az egyes elemek értéke:

• 0 jelöli a még nem bejárt útvonalakat (tehát ahová léphetünk),
• 9 jelöli a falat (tehát ahová nem léphetünk),
• 5 jelöli a célt (ha ide értünk, akkor megvan a megoldás).

     Ezeken kívül a feladat megoldása közben még két értéket vehetnek fel a tömb elemei:

• 1, amely az adott pontig bejárt, helyesnek tűnő útvonalat fogja jelölni,
• 2, amely a mát bejárt, de zsákutcát (tehát nem a kijárathoz vezető) útvonalat fogja jelölni.

     A megoldás keresése a következő lesz:

• Elindulunk a bejáratnál (10.sor, 2. mező) és ezt megjelöljük 1-essel.
• Megnézzük, hogy mehetünk-e felfele (az adott hely feletti mező értéke 0 vagy 5). Ha mehetünk, akkor oda lépünk (tehát azt is bejelöljük 1-essel), majd innen próbálunk tovább lépni. Ha nem mehetünk, akkor hasonlóan megnézzük a jobbra, majd a balra, majd a lefele irányt és abba az irányba megyünk, ahol szabad az útvonal (tehát ahol a tömbben 0 vagy 5 van).
• Ha valamelyik ponttól egyik irányban sem tudunk tovább lépni, akkor ezt a pontot bejelöljük 2-essel (zsákutca), majd visszalépünk az előző pontra, ahonnan próbálunk más irányba továbbmenni (vagy innen is visszalépni, ha nem vezet sehova).

     A megoldás menetének keresését az alábbi animáció szemlélteti:
   
     
   
     Az animációban az 1-es (zöld) jelöli a bejárt és helyes útvonalat, a 2-es (piros) pedig azokat a mezőket, amelyeken keresztül próbáltuk megkeresni a helyes útvonalat, de zsákutcába jutottunk (tehát ezekről vissza kellett lépnünk).
   
     Végül nézzük meg a pascalban megírt programot, mely megkeresi a fenti labirintusban a helyes útvonalat az említett algoritmus szerint:

program Pelda26;
uses crt;

var lab:array [1..10,1..10] of byte
         = ((9,9,9,9,9,9,9,9,9,9),
            (9,0,0,9,0,9,0,9,0,5),
            (9,0,9,9,0,9,0,9,0,9),
            (9,0,0,0,0,9,0,0,0,9),
            (9,9,0,9,9,9,9,9,0,9),
            (9,0,0,0,0,0,0,9,0,9),
            (9,0,9,9,9,0,9,0,0,9),
            (9,0,0,0,9,0,0,0,9,9),
            (9,0,9,0,9,0,9,0,0,9),
            (9,0,9,9,9,9,9,9,9,9));

procedure kiiras;
var i,j:integer;
begin
 for i:=1 to 10 do
  begin
   for j:=1 to 10 do
    case lab[i,j] of
     9: begin {fal}
        textcolor(lightgray);
        write(#219); { #219 = befestett
                      negyzet karakter }
        end;
   0,5: write(' '); { ures vagy celpont }
     1: begin { helyes utvonal }
        textcolor(lightgreen);
        write('X');
        end;
     2: begin { bejart, de rossz utvonal }
        textcolor(red);
        write('O');
        end;
    end;
   writeln;
  end;
 writeln;
end;

procedure lepes(x,y:integer);
begin
 { nem ertunk be a celba? }
 if lab[x,y]<>5 then
  begin
   { lepes elore... }
   lab[x,y]:=1;
   { van felfele bejaratlan utvonal (ures vagy celpont)? }
   if (x>1) and (lab[x-1,y] in [0,5]) then lepes(x-1,y);
   { van jobbra bejaratlan utvonal (ures vagy celpont)? }
   if (y<10) and (lab[x,y+1] in [0,5]) then lepes(x,y+1);
   { van balra bejaratlan utvonal (ures vagy celpont)? }
   if (y>1) and (lab[x,y-1] in [0,5]) then lepes(x,y-1);
   { van lefele bejaratlan utvonal (ures vagy celpont)? }
   if (x<10) and (lab[x+1,y] in [0,5]) then lepes(x+1,y);
   { lepes vissza...
   megjeloles bejart, de rossz utvonalnak }
   lab[x,y]:=2;
  end
 else
  begin
   { celba ertunk, utolso lepes elore... }
   lab[x,y]:=1;
   { megtalalt utvonal kirajzolasa }
   kiiras;
   { utolso lepes vissza }
   lab[x,y]:=2;
  end;
end;

begin
 clrscr;
 { ures labirintus kirajzolasa }
 kiiras;
 { megoldas keresese,
 elso lepes: [10,2] }
 lepes(10,2);
 { magyarazat kiirasa }
 textcolor(lightgray);
 writeln(#219,' ... fal');
 textcolor(red);
 write('O');
 textcolor(lightgray);
 writeln(' ... bejart, de rossz utvonal');
 textcolor(lightgreen);
 write('X');
 textcolor(lightgray);
 write(' ... helyes utvonal');
 { varakozas egy billentyu megnyomasara }
 readkey;
end.

     Az programban megfigyelhettük, hogy miután megtaláltuk a labirintusból kivezető útvonalat, kiírtuk azt a képernyőre, majd tovább folytatódott a keresés. Így tehát, amennyiben a labirintusnak több kijárata is lenne (a tömbben 5-ös számmal jelölve), megtalálnánk mindegyik kijárathoz a kivezető útvonalat.