Skakačev obhod

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Odprt skakačev obhod
Zaključen obhod
Animirana rešitev
Skakačev graf prikazuje vse možne poti za skakačev obhod na standardni šahovnici 8×8. Števila v vsaki točki kažejo število možnih potez iz te točke.

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:

  • iščemo zaključene obhode (po zadnji potezi skakač skoči na začetno polje),
  • uporabimo različne velikosti (in oblike) šahovnice,
  • uporabimo drugačne šahovske figure,
  • uporabimo drugačno topologijo šahovnice.

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 v paskalu[uredi | uredi kodo]

Program v paskalu

program lipicanec(output);
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.

Zunanje povezave[uredi | uredi kodo]