Cesta jezdce po sachovnici (Knight's Tour, Springerproblem) je jedna z klasických sachových úloh. Úkolem je najít takovou cestu, kdy jezdec projde kazdé pole sachovnice práve jednou. Príkladem takové cesty je následující obrázek:
Vytvorte trídu Knight, která bude obsahovat algoritmus nalezení cesty jezdce po sachovnici. Jezdec musí behem své cesty navstívit kazdé pole práve jednou.
#ifndef KNIGHT
#define KNIGHT
#define CHECK
#include <iostream>
#include <iomanip>
using namespace std;
class Knight
{
private:
int** pole;
int velkost;
int** presiel;
public:
Knight(int velkost);
~Knight();
bool runTour(int ,int );
int** getmoves();
bool checkTour(int**, int);
friend ostream& operator <<(ostream&, const Knight&);
};
#endif
#include "knight.h"
//------------------------------------------------------------------------
Knight::Knight(int n):velkost(n)
{
if(n<1)n=1;
pole= new int*[n];
presiel=new int*[n*n];
for(int i=0;i<n;i++)
{pole[i]=new int[n];
for(int j=0;j<n;j++)
pole[i][j]=0;
}
for(int i=0;i<n*n;i++)
presiel[i]=new int[2];
}
//--------------------------------------------------------------------------
Knight::~Knight()
{
for(int i=0;i<velkost;i++)
delete[] pole[i];
for(int i=0;i<velkost*velkost;i++)
delete[] presiel[i];
delete[] pole;
delete[] presiel;
}
//-------------------------------------------------------------------------
bool Knight::runTour(int x,int y) // hledání cesty
{
const int pocet_policok=velkost*velkost;
int i,active_X,active_Y,next_X,next_Y,obsadene=1,moznost=0;
int* tahy=new int[velkost*velkost];
int moznosti[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},
{1,2},{-1,2},{1,-2},{-1,-2}};
if (x<1 ||x>velkost||y<1||y>velkost) return false;
for(i=0;i<(pocet_policok);i++)
{tahy[i]=0;presiel[i][0]=0;presiel[i][1]=0;}
for(i=0;i<velkost;i++)
for(int j=0;j<velkost;j++)
pole[i][j]=0;
pole[x-1][y-1]=1;
presiel[0][0]=x;
presiel[0][1]=y;
// ================= hlavny cyklus ==================================
for(;;)
{
active_X=presiel[obsadene-1][0]-1;
active_Y=presiel[obsadene-1][1]-1;
moznost=tahy[obsadene-1];
if (moznost==8)
{pole[active_X][active_Y]=0;
if (obsadene!=1) obsadene--;
else return false;
tahy[obsadene-1]++;
tahy[obsadene]=0;
continue; }
next_X=active_X+moznosti[moznost][0];
next_Y=active_Y+moznosti[moznost][1];
if (next_X<0||next_X>=velkost||next_Y<0||next_Y>=velkost)
{tahy[obsadene-1]++; //mimo sachovnicu
continue; }
else
{if (pole[next_X][next_Y]!=0) //uz je obsadene
{tahy[obsadene-1]++;continue; }
else {
presiel[obsadene][0]=next_X+1;
presiel[obsadene][1]=next_Y+1;
obsadene++; // mozme ist
pole[next_X][next_Y]=obsadene;
}
}
if(obsadene==pocet_policok) return true;
}
}
//----------------------------------------------------------------------
int** Knight::getmoves() // sekvence polí, tak jak je jezdec prosel
{
return presiel;
}
//---------------------------------------------------------------------
bool Knight::checkTour(int** cesta, int pocet_krokov)
{
int X,Y;
if(pocet_krokov!=velkost*velkost) return false;
for(int i=1;i<pocet_krokov;i++) // skace podla pravidiel ?
{
X=cesta[i-1][0]-cesta[i][0];if (X<0) X=0-X;
Y=cesta[i-1][1]-cesta[i][1];if (Y<0) Y=0-Y;
if(!(((X==1)||(X==2)) && ((Y==1)||(Y==2)) && (X!=Y)))
return false;
}
int** sachovnica=new int*[velkost];
for(int i=0;i<velkost;i++)
{sachovnica[i]=new int[velkost];
for(int j=0;j<velkost;j++)
sachovnica[i][j]=0;
}
for(int i=0;i<pocet_krokov;i++)
{
if (cesta[i][0]<1 ||cesta[i][1]<1||
cesta[i][0]>velkost||cesta[i][1]>velkost)
return false;
if (sachovnica[cesta[i][0]-1][cesta[i][1]-1]==0)
sachovnica[cesta[i][0]-1][cesta[i][1]-1]=i+1;
else
return false;
}
return true;
}
//---------------------------------------------------------------------
ostream& operator <<(ostream& out, const Knight& jazdec)
{
int i,j;
for(i=(jazdec.velkost-1);i>=0;i--)
{out<<setw(2)<<i+1;
for(j=0;j<jazdec.velkost;j++)
{out<<setw(3)<<jazdec.pole[i][j];}
out<<"\n";
}
out<<" ";
for(i=0;i<jazdec.velkost;i++)
{out<<setw(3)<<static_cast<char>(i+97);}
out<<endl;
return out;
}
