Program w C

[Ulala]

Wyznacz taka sekwencje ruchów skoczka szachowego na szachownicy o rozmiarach 8 X 8, ze kazde pole szachownicy jest odwiedzone dokładnie jeden raz.

Czy ktoś z państwa ma na to zadanie jakiś pomysł...? Instrukcję albo coś w tym stylu...
Z góry bardzo dziękuję za pomoc...

[Crizz]

Kod: Zaznacz cały

bool konik(int **T, int i, int j, int N, int pole)
{
      T[i][j]=pole;
      if(pole==N*N) return true;
      if(T[i-2][j-1]==0 AND konik(T,i-2,j-1,int N, pole+1)) return true;
      if(T[i-2][j+1]==0 AND konik(T,i-2,j+1,int N, pole+1)) return true;
      if(T[i+2][j-1]==0 AND konik(T,i+2,j-1,int N, pole+1)) return true;
      if(T[i+2][j+1]==0 AND konik(T,i+2,j+1,int N, pole+1)) return true;
      if(T[i+1][j-2]==0 AND konik(T,i+1,j-2,int N, pole+1)) return true;
      if(T[i+1][j+2]==0 AND konik(T,i+1,j+2,int N, pole+1)) return true;
      if(T[i-1][j+2]==0 AND konik(T,i-1,j+2,int N, pole+1)) return true;
      if(T[i-1][j-2]==0 AND konik(T,i-1,j-2,int N, pole+1)) return true;
      T[i][k]=0;
      return false;
}

To, co widzisz powyżej, to pseudokod, trzeba go minimalnie zmodyfikować, żeby otrzymać kod napisany w C.

Powyższa funkcja sprawdza, czy istnieje taka sekwencja ruchów konika szachowego dla szachownicy NxN, w której konik startuje z pola odpowiadającego elementowi tablicy T[j].

Jako argument należy przekazać funkcji tablicę T (N+4)x(N+4), w której pierwsze dwa i ostatnie dwa rzędy, oraz pierwsze dwie i ostatnie dwie kolumny, wypełnione są wartością -1, a pozostałe pola tablicy wypełnione są zerami (minus jedynki to pola kontrolne, służą do tego, żeby konik nie wyskoczył poza zakres tablicy).

Funkcja konik w przypadku, kiedy prawidłowa sekwencja zostanie znaleziona, nie tylko zwraca wartość true, ale pozostawia tablicę T wypełnioną liczbami całkowitymi, które wyznaczają kolejne pola, na które powinien skoczyć konik (jeśli wywoła się ją dla N=8, tablica zostanie wypełniona liczbami 1,2,3,...,64).

Musisz jeszcze napisać drugą funkcję, która:
*dostaje jako argument tablicę T (12x12)
*wypełnia odpowiednie pola minus jedynkami oraz zerami
*dla (w jakiś sposób) kolejnych "ważnych" par i,j (tzn. \(\displaystyle{ 2 \le i,j \le 9}\)) będzie sprawdzała, czy funkcja konik(T,i,j,8,1) zwraca prawdę (jeśli zwróci prawdę, to twoja funkcja też ma zwrócić prawdę i zakończyć się; zastanów się, którą część spośród "ważnych" pól tablicy trzeba sprawdzić, dla niektórych pól sytuacja jest symetryczna - podpowiedź: którą jedną czwartą)

Mam nadzieję, ze pomogłem, w razie wątpliwości pytaj.

[Fibik]

Takim sposobem z tysiąc lat trzeba będzie czekać.

Na problem konika jest prosty sposób - gotowa metoda, która idzie bez cofania się, czyli złożoność liniowa zamiast 2^n.

Trzeba się po prostu poruszać po minimum, czyli skaczemy na to pole, do którego jest minimum wejść (z sąsiednich pól).

Stoimy na polu (x,y):
1. sprawdzamy kolejno pola, do których możemy skoczyć i liczymy to minimum.
2. jest wole pole: skaczemy do pola z minimum i powtarzamy 1.;
brak: koniec - brak rozwiązania lub sukces, gdy przeszliśmy wszystkie N^2.

[Crizz]

Takim sposobem z tysiąc lat trzeba będzie czekać.

Oczywiście, tylko, że...

Trzeba się po prostu poruszać po minimum, czyli skaczemy na to pole, do którego jest minimum wejść (z sąsiednich pól).

... sądzę, iż Ulala ma prawo oczekiwać od ciebie wyjaśnienia, skąd się wzięła taka heurystyka, zanim przedstawi Twoje rozwiązanie wykładowcy

(jakby mimo wszystko moje rozwiązanie było komuś potrzebne, to przepraszam za deklarację "int N" argumentu funkcji w jej wywołaniu, oczywiście nie powinno jej tam być, tylko samo N; nie wiem czemu nie mogę edytować tego posta).

[Fibik]

Heurystyka działa dla dowolnej matrycy NxN jaką zmieścisz w komputerze, więc sama sobie jest dowodem.

Na dzisiejszym pececie dla N = 100 masz rozwiązanie po kilku milisekundach; dla N = 1000 pewnie około 1s.

Twój sposób będzie wyliczał przypadek 8x8 pewnie kilka minut. Czas rośnie chyba jak 2^(N^2), czyli dla N = 10 wyjdzie już: 2^100/2^64 = 2^36 = 68719476736 razy dłużej.

[Crizz]

Rozumiem i wiem o tym wszystkim. Chodziło mi tylko o to, że skoro autorka tego tematu nie ma pojęcia, jak rozwiązać zadanie, to staram się przedstawić rozwiązanie, na które mogła wpaść sama (nie chodzi o wynik końcowy, tylko o tok rozumowania/sposób rozwiązania).