Question

Algorytm skoczka szachowego rekurencyjny w C++

Answer 1

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 <cstdlib>
#include <iostream>
#include <vector>

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<r; ++i)
for(int j=0; j<r; ++j)
if(tab[i][j] != 1)
return false;

return true;

}

bool skoczek(int a, int b, int** tab, vector<Position> &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<r; ++i)
tab[i] = new int[r];

//poczatkowo zadne z pol nie zostalo odwiedzone
for(int i=0; i<r; ++i)
for(int j=0; j<r; ++j)
tab[i][j] = 0;

//znaleziona trasa skoczka
vector<Position> trasa;

if( skoczek(start.x,start.y,tab,trasa) )
{
//wyswietlenie znalezionej trasy
for(int i=0; i<trasa.size(); ++i)
{
cout<<static_cast<char>(trasa[i].x+65)<<" ";
cout<<trasa[i].y+1<<endl;
}
cout<<endl<<endl;
for(int i=0; i<r; ++i)
for(int j=0; j<r; ++j)
cout<<tab[i][j]<<" ";
}
else
cout<<"Nie znalazlem trasy"<<endl;


//usuniecie zadeklarowanej dynamicznie tablicy
for(int i=0; i<r; ++i)
delete []tab[i];

delete []tab;


system("PAUSE");
return 0;
}