Konik :]

[nightstalker]

Z wieża hanoi mi nikt nie pomógł więć z tym też pewnie zostane sam, ale co tam...

Sprawa wygląda tak:

 

Jest pole 8x8 wypełnione zerami:

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

I jest konik który moze poruszać się tak jak to na konika przystało z każdego pola ma 8 możliwości ruchu. No prawie z każdego bo czasami ogranicza go szachownica :] Możliwości konika prezentują się tak:

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 1 0 5 0 0 0

0 6 0 0 0 4 0 0

0 0 0 K 0 0 0 0

0 2 0 0 0 8 0 0

0 0 7 0 3 0 0 0

0 0 0 0 0 0 0 0

 

Konik startuje z dowolnego miejsca na szachownicy porusza sie po niej zostawiająć po sobie jakiś znak. Po 3 przykładowych ruchach szachownica wygląda tak:

 

1 0 0 0 0 0 0 0

0 0 2 0 0 0 0 0

0 0 0 0 3 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

Zadaniem konika jest przejście całej szachownicy (tablicy) startując z dowolnego pola. Napisałem taki programik wykorzystujący funkcję rekurencyjną:

 

program konik;{$APPTYPE CONSOLE}uses  SysUtils;typeTtab = array[1..4,1..4] of byte;vartablica:Ttab;procedure wypelnij(var tablica:Ttab);var i,j:integer;beginfor i:=1 to 4 dofor j:=1 to 4 dotablica[i,j]:=0;end;procedure rysuj(tablica:Ttab);var i,j:integer;beginfor i:=1 to 4 dobegin;for j:=1 to 4 dowrite(tablica[i,j]:1);writeln;end;end;procedure skocz(x,y:integer;k:integer;tablica:Ttab);beginif ( (x>4) or (x<1) or (y>4) or (y<1) ) then exit;if ( tablica[x,y] = 1 ) then exit;tablica[x,y] := 1;//writeln;//writeln('Krok : ',k);//writeln('Stan :');//rysuj(tablica);//readln;if k = 16 then begin writeln('Sukces!'); exit; end;skocz(x-1, y-2, k+1, tablica);skocz(x-2, y+1, k+1, tablica);skocz(x+1, y+2, k+1, tablica);skocz(x+2, y-1, k+1, tablica);skocz(x+1, y-2, k+1, tablica);skocz(x+2, y+1, k+1, tablica);skocz(x-1, y+2, k+1, tablica);skocz(x-2, y-1, k+1, tablica);end;var i,j:integer;beginfor i:=1 to 4 dofor j:=1 to 4 dobeginwriteln('Jedziemy z parametrami startowymi x=',i,',y=',j,'...');skocz(i, j, 0, tablica);wypelnij(tablica);end;readln;end.

Pytanie: Czy ja mam gdzieś w programie błąd, czy tez jest to niewykonalne zadanie ?

[m4r]

To zadanie jest wykonalne dla zwykłej szachownicy 8x8. Na kilkadziesiąt milionów sposobów. Idź do biblioteki i pożycz sobie "Lilavati". W tej książce jest parę metod na obejście szachownicy.

Ale czy jest dla 4x4 (jak masz w programie), nie wiem.

[nightstalker]

"Lilavati" jutro sobie wypozyczę ( jak bedzie :P ), a 4x4 faktycznie się nie da i to wiem już na 100% ! Wiem też że mój program jest za bardzo złożony i możliwe że przez to się nie wykonuje prawidłowo. Zamiast 8 wywołań rekurencyjnych ponoc wystarczy jedno. To wszystko co narazie znalazłem w sieci na ten temat... Implementacji dalej nie ma, ale szukam...

[Gość sialala]

Ile ja sie narysowalem w liceum tych szachownic z tym konikiem. Znalazlem co najmniej 4 rozne drogi przy starcie z rogu szachownicy. Przy starcie z miejsca startowego konika doszedlem do bodajze 6 roznych drog przejscia calej szachownicy. Wiec zadanie jest jak najbardziej wykonalne. :)

[m4r]

a to próbowałeś przerobić?

Dużo tego jest na necie :]

Src kodu- http://www.ii.uni.wroc.pl/~wzychla/ra2223/ac.html

int szachownica[12][12];int xk,yk,nr,rozwiazanie;void przygotuj_pola(){  int i,j;  for (i=0;i<12;i++)   for (j=0;j<12;j++)szachownica[i][j]=1;  for (i=2;i<10;i++)   for (j=2;j<10;j++)szachownica[i][j]=0;}void umiesc_konika(int x,int y,int numer){  int i,j,k,ch;  if (szachownica[x][y]==0)  {szachownica[x][y]=numer;if (numer==64){ printf("Rozwiazanie: %d\n",rozwiazanie); rozwiazanie++; for (i=2;i<10;i++) {  for (j=2;j<10;j++)  {   printf("%3d ",szachownica[j][i]);  }  printf("\n"); }}umiesc_konika(x+1,y-2,numer+1);umiesc_konika(x+2,y-1,numer+1);umiesc_konika(x+2,y+1,numer+1);umiesc_konika(x+1,y+2,numer+1);umiesc_konika(x-1,y+2,numer+1);umiesc_konika(x-2,y+1,numer+1);umiesc_konika(x-2,y-1,numer+1);umiesc_konika(x-1,y-2,numer+1);szachownica[x][y]=0;  }}void main(){  przygotuj_pola();  xk=2;yk=2;nr=1;rozwiazanie=1;  umiesc_konika(xk,yk,nr);}

[nightstalker]

Ten programik jest bardzo podobny do mojego i ma taką samą złożoność obliczeniową ( 8 wywołań funkcji rekurencyjnej ! ). Ja raczej szukam rozwiązania z jednym wywołaniem, bo wiem że takie istnieje ( gość na wykładzie o tym wspomniał i tym mnie zachęcił do walki z tym zadaniem:P )

[Haquim]

A byłeś na stronie olimpiady informatycznej?

Są tam rozwiązania ogólnie omówione z poprzednich olimpiad - tzw. niebieskie książeczki do ściągnięcia w formie pdf-a

http://www.oi.edu.pl/

Może znajdziesz podobne zadanko