{ Das Haus des Nikolaus, fuer Datenstrukturen, SS03, Benn }
{ Autor: Dipl.-Ing. Thomas Speiser                        }
{ Source from: http://Codes.TurboTools.de                 }

{ Das Haus des Nikolaus
           5 
          / \
         3 - 4
          X  
         1 - 2 }

program nikolaus;
uses Crt;
const t = true;
      f = false;
type aMatrix  = array[1..5,1..5] of boolean;

function nikolaus1: longint;

 procedure backtracking(var m: Amatrix; restkanten,linienzug: longint;
                        var loesungen: longint);
 var von, nach: longint;
     x1,y1,x2,y2: integer;
 begin
      if restkanten = 0 then begin
      inc(loesungen); write(linienzug,' '); end
      else begin
      von:=linienzug mod 10;

{ Visualisieren des Backtracking }

	  x1:=whereX; y1:=whereY;
      gotoxy(0,30);
      for x2:=1 to 5 do begin
        for y2:=1 to 5 do
        if m[x2,y2] then write('t') else write('f');
        writeLN; end;
      gotoxy(0,37); write('VON: ',von,' LINIENZUG: ',linienzug,'                         ');
      gotoxy(x1,y1);
      delay(1000);

{ Visualisieren des Backtracking }

      for nach:=1 to 5 do
      if m[von,nach] then begin
         m[von,nach]:=false;
         m[nach,von]:=false;
      backtracking(m,restkanten-1,10*linienzug+nach,loesungen);
      m[von,nach]:=true;
      m[nach,von]:=true;
      end;
 end;
 end;

var m: Amatrix;
    a,b: longint;
begin
{ aMatrix zuweisen }
m[1,1]:=f; m[1,2]:=t; m[1,3]:=t; m[1,4]:=t; m[1,5]:=f;
m[2,1]:=t; m[2,2]:=f; m[2,3]:=t; m[2,4]:=t; m[2,5]:=t;
m[3,1]:=t; m[3,2]:=t; m[3,3]:=f; m[3,4]:=t; m[3,5]:=t;
m[4,1]:=t; m[4,2]:=t; m[4,3]:=t; m[4,4]:=f; m[4,5]:=f;
m[5,1]:=f; m[5,2]:=t; m[5,3]:=t; m[5,4]:=f; m[5,5]:=f;

    a:=0;
    for b:=1 to 5 do begin
    writeLN('Linienzug die in Ecke ',b,' beginnen');
    backtracking(m,8,b,a);
    writeLN;
    end;
    nikolaus1:=a;
end;

begin
ClrScr;
TextMode(CO80 xor Lo(LastMode)+Font8x8 xor LASTMODE);
writeLN('Backtracking - Demo');
writeLN;
writeLN(nikolaus1);
readLN;
end.