Skakačev obhod
Orodja
Splošno
Tiskanje/izvoz
V drugih projektih
Skakačev obhod je matematični problem s skakačem na standardni šahovnici (8×8). Skakača postavimo na poljubno začetno polje in z njim obiščemo vsa ostala polja na deski.
Obstaja več milijard rešitev. V okoli 122.000.000 rešitvah se skakač vrne na isto polje, od koder je začel.
Problem, ki so ga proučevali mnogi matematiki, tudi Euler, lahko posplošimo v več smeri:
Obstajajo tudi igre za enega ali več igralcev na to temo.
Skakačev obhod je primer bolj splošnega iskanja Hamiltonove poti v teoriji grafov, ki je NP-poln. Zaključen skakačev obhod pa je primer Hamiltonovega cikla.
program lipicanec(output); [[Niklaus Wirth|Wirth N.]], Računalniško programiranje I} const n=8; nsq=n*n; {deska 8x8} xz=1; yz=1; {zacetni koordinati} type index=1...n; var i,j : integer; q : boolean; s : set of index; a,b : array[1...8] of integer; {osem moznih skokov} h : array[index,index] of integer; m : integer; procedure izpis; {resitve} var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do write(h[i,j]:4); writeln; end; end; {izpis} procedure try(i:integer; x,y:index; var q:boolean); var k,u,v : integer; q1:boolean; begin k:=0; repeat k:=k+1; q1:=false; u:=x+a[k]; v:=y+b[k]; if (u>=1) and (u<=n) and (v>=1) and (v<=n) then if h[u,v]=0 then begin h[u,v]:=i; if i<nsq then begin try(i+1,u,v,q1); {rekurzivni klic} if not q1 then h[u,v]:=0; end else q1:=true; end; until (q1 or (k=8)); q:=q1; end;{try} begin s:=[1...n]; begin a[1]:= 2; b[1]:= 1; a[2]:= 1; b[2]:= 2; a[3]:=-1; b[3]:= 2; a[4]:=-2; b[4]:= 1; a[5]:=-2; b[5]:=-1; a[6]:=-1; b[6]:=-2; a[7]:= 1; b[7]:=-2; a[8]:= 2; b[8]:=-1; for i:=1 to n do for j:=1 to n do begin h[i,j]:=0; end; h[xz,yz]:=1; try(2,xz,yz,q); if q then izpis else writeln('Ni rešitve!'); end; end.