Matematické Fórum

Ahoj, pokouším se o napsání programu, řešící backtrackingem následující problém, nicméně jsem se v programu zamotal, a prožil dost chvilek beznaděje.

Problém zní následovně : Řeka. Na jednom břehu je pasáček ovcí, vlk, koza, zelí a lodička. Vlk by rád sežral kozu, koza si dělá zálusk na zelí. Do lodičky může pasáček vzít jen jedno zvíře nebo zelí. Dvě zvířata nebo zvíře a zelí se na lodičku najednou nevejdou. Koza ani vlk pádlovat překvapivě neumí.
Jak dostane pasáček vlka, kozu i zelí na druhou stranu tak, aby na jednom břehu nikdy nebyla koza s vlkem nebo se zelím bez dohledu pasáčka?

Snažil jsem se to řešit přes stavový strom, řádně okomentovaný kód viz níže :
________________________________________________________________________________

program vkz_podruhe;
uses crt;
type uprvek = ^prvek;     //lineární spojový seznam - pokud jsme stav už prošli, uloží se do něj v tomto tvaru
     prvek=record
     stav:array[1..4] of integer;
     je_pripustne:boolean;
     dalsi:uprvek;
     end;

var
stav:array[1..4] of integer; //0 - levy breh, 1 - pravy breh... 1. vlk 2.koza 3.zeli 4. prevoznik
hlava:uprvek;
zarazka:uprvek;
novy:uprvek;
cache:record                //pokud funkce "najdi" v seznamu prvek našla, uloží ho sem
     stav:array[1..4] of integer;
     je_pripustne:boolean;
     end;

procedure init();           //nacte seznam
var i:integer;
begin
  for i:=1 to 4 do stav[i] := 0;
  new(hlava);
  new(zarazka);
  hlava^.dalsi := zarazka;
  zarazka^.dalsi := nil;
end;
procedure vloz(vlk:integer;koza:integer;zeli:integer;prevoznik:integer;pripustnost:boolean); //vlozi prvek do seznamu
var pom:uprvek;
begin
  new(novy);
  pom := hlava^.dalsi;
  hlava^.dalsi := novy;
  novy^.dalsi := pom;
  novy^.stav[1] := vlk;
  novy^.stav[2] := koza;
  novy^.stav[3] := zeli;
  novy^.stav[4] := prevoznik;
  novy^.je_pripustne := pripustnost;
end;
function najdi(vlk:integer;koza:integer;zeli:integer;prevoznik:integer):boolean;    //pokud se prvek v seznamu nachází, hodí true a uloží ho do proměnné "cache" pokud ne, hodí false
var pom:uprvek;
begin
  pom := hlava^.dalsi;
  if hlava^.dalsi <> zarazka then begin
     while pom^.dalsi <> zarazka do begin
      if pom^.stav[1] = vlk then if pom^.stav[2] = koza then if pom^.stav[3] = zeli then if pom^.stav[4] = prevoznik then begin
       najdi := true;
       cache.stav[1] := vlk;
       cache.stav[2] := koza;
       cache.stav[3] := zeli;
       cache.stav[4] := prevoznik;
       cache.je_pripustne := pom^.je_pripustne;
      end else
      najdi := false;
    end;
  end else najdi := false;
end;
function presun(co:integer):integer;
begin
if co = 1 then presun := 0;
if co = 0 then presun := 1;
end;
procedure endcheck(vlk:integer;koza:integer;zeli:integer;prevoznik:integer);  //jsme v cíli?
begin
    if vlk=1 then if koza=1 then if zeli=1 then if prevoznik = 1 then begin
     repeat until keypressed;
     halt;
     end;
end;

procedure vkz(vlk:integer;koza:integer;zeli:integer;prevoznik:integer);
var vkzb:boolean; //sezerou se?
    vysledek_hledani:Boolean; [b]//pomocná proměnná, říkající nám výsledek funkce "najdi" abychom nemuseli procházet seznam víckrát[/b]
begin
   writeln(vlk,' ',koza,' ',zeli,' ',prevoznik);
   endcheck(vlk,koza,zeli,prevoznik); //ověřujeme, jestli jsme v cíli
  vkzb:= true;
  if (vlk = 1) and (koza = 1) and (prevoznik = 0) then vkzb := false;
  if (koza = 1) and (zeli = 1) and (prevoznik = 0) then vkzb := false;
  if (vlk = 0) and (koza = 0) and (prevoznik = 1) then vkzb := false;
  if (koza = 0) and (zeli = 0) and (prevoznik = 1) then vkzb := false;    //overujeme jestli je tento stav pripustny

  if najdi(vlk,koza,zeli,prevoznik) = false then begin //tato podmínka prohledá seznám a zjistí, jestli jsme tento stav už prošli
  vloz(vlk,koza,zeli,prevoznik,vkzb);
  vysledek_hledani:= false;
  end else
  vysledek_Hledani:= true;

  if vysledek_hledani = false then if vkzb = true then begin    //pokud jsme tento stav ještě neprošli, a je přípustným částečným řešením, začneme rekurzivně zkoumat jeho podstavy
     vkz(presun(vlk),koza,zeli,presun(prevoznik));
     vkz(vlk,presun(koza),zeli,presun(prevoznik));
     vkz(vlk,koza,presun(zeli),presun(prevoznik));
     vkz(vlk,koza,zeli,presun(prevoznik));
    end else
    if cache.je_pripustne = true then begin        //pokud jsme tento stav už prošli, a je přípustným částečným řešením, rekurzivně zkoumáme jeho podstavy
     vkz(presun(vlk),koza,zeli,presun(prevoznik));
     vkz(vlk,presun(koza),zeli,presun(prevoznik));
     vkz(vlk,koza,presun(zeli),presun(prevoznik));
     vkz(vlk,koza,zeli,presun(prevoznik));
    end else  //zde nevím, jak pokračovat   //pokud jsme tento stav už prošli, a není přípustným částečným řešením,backtrackujeme
end;
begin
  init;
  vkz(0,0,0,0);
  repeat until keypressed;
end.
__________________________________________________________________________________

Teoreticky sice úlohu znám, ale dát to do kódu je už horší. Rád bych, kdyby mi někdo poradil, jak toto dokončit. Popř, jak na to jít znova od začátku, byl bych moc vděčný. Díky.