Problem skoczka (konika) szachowego

Odpowiedz Nowy wątek
2006-12-09 09:58
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 ?

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

Pozostało 580 znaków

2006-12-09 11:13
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).


<span style="color: blue">"Kolarstwo to jedna z najtrudniejszych dyscyplin sportu. Nawet najgorszy kolarz jest wciąż wybitnym sportowcem."
s.p. Marco Pantani
</span>

Pozostało 580 znaków

2006-12-09 11:59
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;

}

Pozostało 580 znaków

2006-12-14 23:22
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.

Pozostało 580 znaków

2006-12-17 11:51
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 !

Pozostało 580 znaków

2006-12-27 19:23
0

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


play hard..go pro.

Pozostało 580 znaków

2007-05-07 13:05
vha
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"

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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