Zdrawim potreboval by som pomoct s upravenim zdrojového kódu:(Zdrojovy kod je implementovany v jazyku c++):
Je dána sachovnica o rozmeroch n x n.
Na sachovnici umiestníme do lubovolnj pozicie šachového kona, jazdce, ktorý sa pohybuje podla známých sachových pravidiel.
Úloha spocívá v tom, ze máme najst cestu kona po sachovnici tak, ze kazdé polícko navstíví iba raz tj. žiadné pole sa neopakuje a ziadné pole nieje vynechane.
Kód:
#include <stdio.h>
//najmensia sachovnice musi byt 5
//najvetsia sachovnica musi byt 8
//velkost sachovnice
const int BoardSize = 8;
//deklaracia typu sachovnice
typedef int tBoard[BoardSize][BoardSize];
//pocet moznych tahov
const int NoOfHorseMoves = 8;
//zmeny suradnic pre jednotlive tahy
const int RowMoveDelta[NoOfHorseMoves] = {-2, -1, +1, +2, +2, +1, -1, -2};
const int ColMoveDelta[NoOfHorseMoves] = {+1, +2, +2, +1, -1, -2, -2, -1};
//deklaracia typu pre ulozenie pozicie
struct Position
{
int Row;
int Col;
};
//inicializacia sachovnice
void InitBoard(tBoard& Board)
{
for(int i = 0; i < BoardSize; i++)
for(int j = 0; j < BoardSize; j++)
Board[i][j] = 0;
}
//zobrazenie sachovnice
void PrintBoard(const tBoard& Board)
{
for(int i = 0; i < BoardSize; i++)
{
for(int j = 0; j < BoardSize; j++)
printf("%4i", Board[i][j]);
printf("\n");
}
printf("\n");
}
//posun kona po sachovnici
Position Move(const Position& Pos, const int MoveIndex)
{
Position p;
p.Row = Pos.Row + RowMoveDelta[MoveIndex];
p.Col = Pos.Col + ColMoveDelta[MoveIndex];
return p;
}
//test ci je tah platny
//vracia true pokial je tah na pozicii Pos na sachovnici dane parametrom Board mozny
bool IsValidMove(const Position& Pos, const tBoard Board)
{
bool Result = true;
Result &= 0 <= Pos.Row;
Result &= Pos.Row < BoardSize;
Result &= 0 <= Pos.Col;
Result &= Pos.Col < BoardSize;
Result &= Board[Pos.Row][Pos.Col] == 0;
return Result;
}
//rekurzivne hledanie riesenie problemu metoda backtracking
// Parametre:
// Board -- aktualna sachovnica, 0 znamena volne policko, cislo rozne od 0 znamena poradie tahu ktorym sa sem kon dostal
// CurrentPos -- aktualna poloha kona
// MoveNumber -- poradie tahu, ktory prevadzame
// Funkcia vracia true , pokial bolo najdene riesenie
bool Horse(tBoard& Board, const Position& CurrentPos,
const int MoveNumber)
{
if (MoveNumber == BoardSize*BoardSize)
return true;
for(int i = 0; i < NoOfHorseMoves; i++)
{
Position p = Move(CurrentPos, i);
if (IsValidMove(p, Board))
{
Board[p.Row][p.Col] = MoveNumber;
if (Horse(Board, p, MoveNumber+1))
return true;
else
Board[p.Row][p.Col] = 0;
}
}
return false;
}
void main()
{
tBoard Board;
Position InitPos = {0,0};
InitBoard(Board);
bool HasSolution = Horse(Board, InitPos, 1);
if (HasSolution)
{
PrintBoard(Board);
}
else
{
printf("Riesenie nenajdene!\n");
}
}
Tento kód funguje pre normalný typ sachovnice ale ked zmenim typ sachovnice na tvar toroidu? tak to nefunguje a cel by som to pomoct upravit aby to fungovalo na sachovnici tvaru n x n a tvaru toroidu...
Vazne by som vám bol vdačný za pomoc poprípade by som bol ochotný za neakú finančnú odmenu.
