|
|
Formalne badania nad problemem skoczka rozpoczęły się
od Leonharda Eulera, który w 1759 roku rozważał go na szachownicy 8x8.
Rozwiążemy bardzo znane zadanie:
Umieszczamy konika szachowego na planszy.
Wykonując tylko dozwolone dla konika ruchy odwiedzimy każde pole dokładnie raz.
|
Dopuszczalne ruchy, przedstawia schemat obok (o ile oczywiście mieszczą się w szachownicy).
Obok aplet z rozwiązaniem na planszy 5x5. ( plansze większe powodują wydłużenie czasu pracy algorytmu ).
Myszą możesz wskazać nowy węzeł startowy. Jak łatwo się przekonać rozwiązanie istnieje gdy początek wyznaczymy w polu oznaczonych jasnym kolorem ( dla planszy 5x5, rzecz jasna ).
Opcja "pokaz dynamiczny" kończy się w sensownym czasie jeśli początek to pole (4,1) - prawe górne, może jeszcze (5,5)-prawe dolne.
|
Zadanie zwykle rozwiązuje się powszechnie znanym algorytmem z powrotami.
Oto jego zasada:
- kolejne kroki, które mogłyby doprowadzić do rozwiązania końcowego, są zapisywane, później zaś, w chwili ujawnienia faktu, że konkretny krok nie zmierza do rozwiązania końcowego (prowadzi w ślepą uliczkę), odpowiednie zapisy są usuwane.
|
Możemy tę zasadę przełożyć na następującą implementację - obok pseudokod "ideowy" :
Punkt ruchy[ ]=new Punkt[9];
int szach[ ][ ]=new int[10][10];
//------------------------------------------
void zeruj( )
{
for(int i=0;i<9;i++)
ruchy[i]=new Punkt(0,0);
for(int i=0;i<10;i++)
for(int j=0;j<10;j++) szach[i][j]=0;
ruchy[0].war(2,1);
ruchy[1].war(1,2);
ruchy[2].war(-1,2);
ruchy[3].war(-2,1);
ruchy[4].war(-2,-1);
ruchy[5].war(-1,-2);
ruchy[6].war(1,-2);
ruchy[7].war(2,-1);
szach[xp][yp] = 1;
}
//-----------------------------------------
int ruch(int nr, int x, int y)
{int nx,ny,licznik=-1;
do
{
licznik++;
nx=x+ruchy[licznik].x;
ny=y+ruchy[licznik].y;
if(nx>=0&&nx<n&&ny>=0&&ny<n)
if(szach[nx][ny]==0)
{
szach[nx][ny]=nr;
if(nrRuchu<n*n)
{
if(ruch(nr+1,nx,ny)==0) return 0;
else
szach[nx][ny]=0;
} else return 0;
}
}
while(licznik!=8);
return 1;
}
|
void ruch()
{
zapoczątkuj wybieranie kandydatów;
do
{
wybierz następnego kandydata;
if(dopuszczalny)
{
zapisz go;
if(rozwiązanie niepełne)
{
ruch wykonać następny krok;
if(próba nieudana) usuń zapis
}
}
}
while (próba udana) lub (brak nast.kandydata)
}
|
Do zapamiętanie dopuszczalnych ruchów skoczka użyłem zmiennej o nazwie ruch klasy Punkt (patrz artykuł "Implementacja w Javie"). Zwykła tablica dwuwymiarowa int[9][2] oczywiście też "załatwia sprawę".
Do pokazania znalezionej trasy wygodną strukturą, wydaje się być, lista (stos) np taka jak zaprezentowano w tym opracowaniu.
Osoby spostrzegawcze zauważyły pewnie, że w Javie tablica ruchy ma wymiar"9", w C++ wystarczy 8 !.
wszystko przez instrukcję :
if(ruch(nrRuchu+1,nx,ny)==0) return 0;
Java "źle " znosi przekraczanie zakresu tablic (inne języki też). Wniosek taki, że lepiej zwiększyć rozmiar ....
Zobacz jeszcze na koniec wersję C++/Dev-C++
|