Problem skoczka (konika) szachowego

0

Mam do napisania na zaliczenie program rozwiązujący problem skoczka na standardowej szachownicy 8x8. Napisałem prosty rekurencyjny brute force, jednak algorytm jest wolny (pierwsze rozwiązanie znajduje w pare minut na procku 2 GHz), a moja ambicja celuje w coś lepszego.

Problem polega na tym, aby przejść przez wszystkie pola poruszając się ruchem konika szachowego tak, aby na każdym polu stanąć dokładnie jeden raz. Szachownice i możliwe ruchy można przedstawić za pomocą nieskierowanego nieważonego grafu o 64 wierzchołkach, a problem sprowadza się do znalezienia ścieżki Hamiltona w tym grafie.

Znacie jakiś konkretny algorytm rozwiązania tego problemu. Zapewne ktoś już się zajmował tym problemem - jak go rozwiązaliście ? Jakie są wasze sugestie ?

na razie znalazłem to, jednak kod jest bardzo rozległy, pisany w c i ciężko się go czyta. Trudno wyłapać punkty kluczowe algorytmu.

0

Może ta strona Ci pomoże. Jest tam archiwum konik.zip. Całość w pascalu (z użyciem Turbo Vision - które możesz sobie podarować, bo to tylko interface usera).

0
Oleksy_Adam napisał(a)

Może ta strona Ci pomoże. Jest tam archiwum konik.zip. Całość w pascalu (z użyciem Turbo Vision - które możesz sobie podarować, bo to tylko interface usera).
Niestety :/ jest tam tylko brute force, który już wcześniej napisałem, dla chętnych:

#include <iostream>
#include <vector>
#include <memory.h>
#include <time.h>

#define ROZMIAR1 6
#define ROZMIAR2 6

typedef short dualshort[2];

const dualshort KIERUNKI[] = {
   { 1, 2},
   {-1, 2},
   { 1,-2},
   {-1,-2}
};

using namespace std;

bool zajete[ROZMIAR1][ROZMIAR2];

bool ruch(int x, int y, int nr_ruchu)
{
   if(nr_ruchu == ROZMIAR1 * ROZMIAR2) return true;

   if(!zajete[x][y])
   {
      //cout << nr_ruchu << " ruch na pole " << x + 1 << ',' << y + 1 << endl;
      zajete[x][y] = true;
      nr_ruchu++;

      int nowy_x, nowy_y;

      for(int i = 0; i < 4; i++)
      {
         nowy_x = x + KIERUNKI[i][0];
         nowy_y = y + KIERUNKI[i][1];

         if(i % 2) { if(nowy_x < 0) continue; }
         else { if(nowy_x >= ROZMIAR1) continue; }
         if(i / 2) { if(nowy_y < 0) continue; }
         else { if(nowy_y >= ROZMIAR2) continue; }
         if(ruch(nowy_x, nowy_y, nr_ruchu))
         {
            cout << "znaleziony ruch na pole " << x + 1 << ',' << y + 1 << endl;
            return true;
         }
      }
      for(int i = 0; i < 4; i++)
      {
         nowy_x = x + KIERUNKI[i][1];
         nowy_y = y + KIERUNKI[i][0];

         if(i / 2) { if(nowy_x < 0) continue; }
         else { if(nowy_x >= ROZMIAR1) continue; }
         if(i % 2) { if(nowy_y < 0) continue; }
         else { if(nowy_y >= ROZMIAR2) continue; }
         if(ruch(nowy_x, nowy_y, nr_ruchu))
         {
            cout << "znaleziony ruch na pole " << x + 1 << ',' << y + 1 << endl;
            return true;
         }
      }
      zajete[x][y] = false;
   }
   return false;
}

void znajdz(int start_x, int start_y)
{
   memset(zajete, 0, sizeof(zajete));
   if(ruch(start_x - 1, start_y - 1, 0))
      printf("Znaleziono");
   else
      printf("Nieznaleziono");
}

int main(int argc, char *argv[])
{
    int x, y;
    time_t t;

    cout << "Podaj polozenie poczatkowe skoczka w szachownicy " << ROZMIAR1 << " na " << ROZMIAR2 << ".\n-wiersz: ";
    cin >> x;
    cout << "\n- kolumna: ";
    cin >> y;

    time(&t);
    znajdz(x, y);
    t = time(NULL) - t;
    cout << "\nczas: "  << (int) t << "sek.";
    return 0;
}
0

Hmm... Wczoraj na ćwiczeniach to mieliśmy i gościu mówił, że jest jakiś algorytm znajdujące jakieś rozwiązanie w parę minut nawet dla planszy 50x50... tylko zapomniałem co to za algo. ;]
Z tego co pamiętam, przyspieszenie w znajdowaniu pierwszego rozwiązania opierało się na tym, że pewne ruchy (w zależności chyba od aktualnego położenia) powinny być najpierw przetwarzane rekurencyjnie.

0

No właśnie, ale które ? Próbowałem różnych kombinacji i różnych taktyk, jednak nie dawały one wyraźnych efektów polepszenia.
Już bardzo długo szukam rozwiązania, nawet wyszukiwarka google mnie zawiodła !

0

mam ten sam projekt ten sam problem :) ja z kolei nie bardzo rozumiem w ktorym momencie algorytm "daje sobie spokoj" i konczy prace..... :)

0

Co prawda odkopuje temat ale może przyda się to komuś :

Cały myk polega na tym że z danego pola można wykonać różną ilość skoków( w różne kierunki) np. z D4 może skoczyć na 8 innych pól a z A1 tylko na dwa.
No i chodzi o to żeby skoczek poruszał po polach o jak najmniejszym możliwości wyboru. np. z C2(6 możliwości) powinien skoczyć na A1 ( 2 możliwości).
najlepiej na wstępie zapisać do tablicy wartości pól:
2,3,4,4,4,4,3,2,
3,4,6,6,6,6,4,3,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
3,4,6,6,6,6,4,3,
2,3,4,4,4,4,3,2,
a potem po każdym skoku je aktualizować.

na polskich stronach jest mało na ten temat. polecam szukanie w google z hasłem "knight tour"

1 użytkowników online, w tym zalogowanych: 0, gości: 1