SimonFudaxian
New Coder
Knight's Closed Tour (a classic programming problem)
C++:
// Moves are made by the lowest accessility points (1 - 8)
int mStart[64], mEnd[64], mIndex[336];
int mRate[] = {2,3,4,4,4,4,3,2,3,4,6,6,6,6,4,3,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,4,6,8,8,8,8,
6,4,4,6,8,8,8,8,6,4,3,4,6,6,6,6,4,3,2,3,4,4,4,4,3,2};
string mNum[64],nNum[] = {" 0"," 1"," 2"," 3"," 4"," 5"," 6"," 7"," 8"," 9","10","11","12",
"13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28",
"29","30","31","32","33","34","35","36","37","38","39","40","41","42","43","44",
"45","46","47","48","49","50","51","52","53","54","55","56","57","58","59","60",
"61","62","63","64"};
void Tour2()
{
int k1, k2, n1, aMove,aStart, aEnd, aMin;
string x1, aTour;
char c1[64];
aMove = 0; // Use 0-63 to represent the chessboard. Knight's first move is cell 0
aTour = mNum[aMove];
for (k2 = 2; k2 <= 64; k2++)
{
mRate[aMove] = 99; aMin = 9; // When a move is picked, the cell is assign 99 points.
aStart = mStart[aMove]; aEnd = mEnd[aMove];
for (k1 = aStart; k1 <= aEnd; k1++)
{
n1 = mIndex[k1]; mRate[n1] = mRate[n1] - 1;
if (aMin > mRate[n1])
{
aMin = mRate[n1]; aMove = n1; //Check out which one is the smallest
}
}
aTour = aTour + mNum[aMove];
}
}
// The Knight's Closed Tour is completed.
cout << "Knight's Closed Tour (classic programming problem)" << endl;
cout << "ASCII characters representing Arabic Numbers" << endl;
cout << aTour << endl;
cout << "The first four moves: 0:4> = 0,10,4,13." << endl << endl;
string aShow[64];
aTour.copy(c1,64);
x1 = ""; // Format the 64 moves.
for (k1 = 0; k1 <= 63; k1++)
{
n1 = int(c1[k1]) - 48;
aShow[n1] = nNum[k1 + 1] + " ";
}
x1 = "";
for (k1 = 0; k1 <= 63; k1++)
x1 = x1 + aShow[k1];
n1 = 0;
for (k2 = 1; k2 <= 8; k2++)
{
cout << " " << x1.substr(n1,24) << endl;
n1 = n1 + 24;
}
}
void SetUp1()
{
int k1, k2, n1, n2, n3, aCount = -1, aFilter[64], bFilter[120];
int aStep[] = {12,-21,-19,21,-12,-8,19,8}; // Use this to build a 2D structure to get in-bound moves only
string x1, x2;
for (k1 = 0; k1 <= 63; k1++) //Format Arabic
mNum[k1] = char(k1+48);
for (k1 = 0; k1 <= 119; k1++) //Set up a filter. 64 represents nothing
bFilter[k1] = 64;
for (k2 = 21; k2 <= 91; k2+= 10) // Set up a 2-D structure for filtering
{
for (k1 = k2; k1<= k2 + 7; k1++)
{
aCount = aCount + 1;
aFilter[aCount] = k1;
bFilter[k1] = aCount;
}
}
aCount = -1;
for (k2 = 0; k2<= 63; k2++)
{
n1 = aFilter[k2];
mStart[k2] = aCount + 1;
for (k1 = 0; k1<= 7; k1++)
{
n2 = n1 + aStep[k1];
n3 = bFilter[n2];
if (n3 != 64)
{
aCount = aCount + 1;
mIndex[aCount] = n3; //Pick up in-bound moves only
}
}
mEnd[k2] = aCount; //mStart and mEnd for quick and easy retrieval of moves
}
}
Last edited by a moderator:
