Poniżej zamieszczam swój algorytm. Niestety ze względu na to, że jest to algorytm rekurencyjny na wynik trzeba czekać od kilkunastu do kilkudziesięciu minut. Nie mam możliwości odpalenia algorytmu na wydajniejszej maszynie, dlatego nie doczekałem się wyniku. Nie mam też 100% pewności, czy algorytm jest poprawny, ale możesz się przynajmniej na czymś wzorować.
#include
#include
#include
using namespace std;
//struktura opisujaca pozycje skoczka
struct Position
{
int x;
int y;
};
//zmienna przechowujaca pozycje startowa skoczka
Position start;
//rozmiar szachownicy
const int r = 8;
//funkcja sprawdza, czy kazde z pol zostalo 1 raz odwiedzone
bool koniec (int** tab)
{
for(int i=0; i &trasa)
{
//sprawdzamy, czy nie wyszlismy poza plansze
if(a<0 || a>=r || b<0 || b>=r)
return false;
//warunek zakonczenia obliczen
if(a==start.x && b==start.y && koniec(tab))
return true;
//sprawdzamy czy pole nie bylo juz odwiedzane
if(tab[a][b]>0)
return false;
//zwiekszamy licznik odwiedzin
tab[a][b]++;
//dodanie aktualnej pozycji do trasy
Position aktualna;
aktualna.x = a;
aktualna.y = b;
trasa.push_back(aktualna);
if( skoczek(a-1, b+2, tab, trasa) )
return true;
if( skoczek(a+1, b+2, tab, trasa) )
return true;
if( skoczek(a-1, b-2, tab, trasa) )
return true;
if( skoczek(a+1, b+2, tab, trasa) )
return true;
if( skoczek(a-2, b-1, tab, trasa) )
return true;
if( skoczek(a-2, b+1, tab, trasa) )
return true;
if( skoczek(a+2, b-1, tab, trasa) )
return true;
if( skoczek(a+2, b+1, tab, trasa) )
return true;
//usuniecie tych odwiedzin
tab[a][b]--;
//usuniecie tego ruchu z trasy
trasa.pop_back();
return false;
}
int main(int argc, char *argv[])
{
//pozycja startowa skoczka
start.x = 4;
start.y = 4;
//tablica przechowująca liczbę odwiedzin danego pola
int** tab = new int*[r];
for(int i=0; i trasa;
if( skoczek(start.x,start.y,tab,trasa) )
{
//wyswietlenie znalezionej trasy
for(int i=0; i(trasa[i].x+65)<<" ";
cout<
