Problem konika szachowego

Przedstawiony poniżej program służy do rozwiązywania problemu konika szachowego, czyli stwierdzenia, czy daną kwadratową planszę o rozmiarze podanym jako parametr, zaczynając z pola o zadanych współrzędnych, daje się obejść ruchem konika szachowego tak, aby na każdym polu znaleźć się dokładnie raz. Jako parametry przyjmuje on rozmiar planszy (zmienna globalna size) oraz współrzędne startowe (startx i starty).

Dodatkowym parametrem jest zmienna depth określająca głębokość drzewa, którą na początku ma sprawdzić procesor główny. Następnie dla każdego liścia w tym drzewie uruchamiany jest procesor wirtualny, który prowadzi dalsze obliczenia (zaimplementowany algorytm polega na rekurencyjnym przeglądaniu drzewa wszystkich możliwych rozwiązań).

Jeśli nie ma rozwiązania danego problemu, to po zakończeniu obliczeń zmienna answer przyjmie wartość 0. Jeśli rozwiązanie istnieje, jej wartość będzie wynosić 1, a dodatkowo w tablicy plansza zapisany będzie odpowiedni sposób obejścia planszy (wartość zapisana w komórce to numer ruchu w którym konik znajduje się na danym polu).

// wielkość planszy

shared size;

// początkowe współrzędne

shared startx; shared starty;

// ilość początkowych iteracji

shared depth;

// czy jest rozwiązanie

shared answer;

// plansza

shared board[1..128,1..128];

// ilość procesorów

shared proc_num;

 

local local_size;

local local_board[1..128,1..128];

local proc;

 

shared tracks[0..63,1..64,1..2];

 

local track[1..64,1..2];

local tr_nr;

local tr_len;

local xp; local yp;

//----------------------------------

// funkcja przygotowująca planszę

function prepare_board()

local x; local y;

local tr[1..65,1..2];

local i;

begin

local_size:=size;

for x:=1 to local_size do

for y:=1 to local_size do

local_board[x,y]:=0;

  

blockread(tracks[proc],tr,128);

i:=1;

while tr[i,1]<>0 and i<65 do

begin

xp:=tr[i,1];

yp:=tr[i,2];

local_board[xp,yp]:=i;      

i:=i+1;

end;

tr_len:=i-1;

end;

//----------------------------------

function step(x,y)

local nx; local ny;

begin

// zaznacz

local_board[x,y]:=tr_len; 

// jeśli koniec - to OK

if tr_len=pow2(local_size) then return 1;

  

// jeśli nie to kolejny krok

tr_len:=tr_len+1;

  

nx:=x-2; ny:=y-1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x-1; ny:=y-2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x+1; ny:=y-2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and 

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x+2; ny:=y-1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x+2; ny:=y+1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x+1; ny:=y+2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

nx:=x-1; ny:=y+2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

 

nx:=x-2; ny:=y+1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

if step(nx,ny)=1 then return 1;

  

// posprzątaj

local_board[x,y]:=0;

tr_len:=tr_len-1;

  

return 0;

end;

//----------------------------------

function controlled_step(x,y,depth,tr_len)

local nx; local ny;

begin

track[tr_len,1]:=x;

track[tr_len,2]:=y;

if depth=0 then

begin

track[tr_len+1,1]:=0;

track[tr_len+1,2]:=0;

blockwrite(track,tracks[tr_nr],(tr_len+1)*2);

tr_nr:=tr_nr+1;

end;

else

begin

local_board[x,y]:=tr_len;

  

nx:=x-2; ny:=y-1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x-1; ny:=y-2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x+1; ny:=y-2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x+2; ny:=y-1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x+2; ny:=y+1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x+1; ny:=y+2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x-1; ny:=y+2;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

      

nx:=x-2; ny:=y+1;

if nx>0 and nx<=local_size and ny>0 and ny<=local_size and

   local_board[nx,ny]=0 then

controlled_step(nx,ny,depth-1,tr_len+1);

  

local_board[x,y]:=0;

end;

  

track[tr_len,1]:=0;

track[tr_len,2]:=0;    

end;

//----------------------------------  

function prepare_tracks(xp,yp,depth)

local x; local y;

begin

local_size:=size;

for x:=1 to local_size do

for y:=1 to local_size do

local_board[x,y]:=0;

for x:=1 to depth+1 do

begin

track[x,1]:=0;

track[x,2]:=0;

end;

tr_nr:=0;

controlled_step(xp,yp,depth,1);

proc_num:=tr_nr;

end;

//----------------------------------

begin

answer:=0;

prepare_tracks(startx,starty,depth);

for proc:=0 to proc_num-1 pardo

begin

prepare_board();

if step(xp,yp)=1 then

  begin

    answer:=1;

    blockwrite(local_board,board,16384);

  end;

end;

end.