The duty is actually advanced: Navigating a knight round a chessboard, visiting every sq. however by no means the identical sq. twice. It took me some time to code, and I don’t suppose my answer is especially elegant, however it works.
As I wrote in final week’s Lesson, my answer includes utilizing the Warnsdorff’s rule. I discovered this heuristic to be stable sufficient that I didn’t want to make use of recursion: A easy loop counting all of the squares within the chessboard is enough to unravel the issue.
Sure, utilizing a loop as a substitute of recursion frightened me, however the rattling factor works, as seen by the animation in Determine 1.
Determine 1. An animation of my answer for the Knight’s Tour.
Within the determine, you see the Knight begin at a random place. Values beginning at zero plot the knight’s path across the chessboard, by no means visiting the identical sq. twice. The ultimate sq. is numbered 63.
The primary main change I produced from the code in final week’s Lesson is to make the board[] array (previously within the chess_board() operate) exterior. Whereas I’m not a fan of exterior variables, this transfer made calling the assorted capabilities lots simpler.
Additional, the chess_board() operate now has no arguments. It outputs the board setting numbers on the positions the place the knight has already moved. An snprintf() operate outputs the knight’s motion values. If a sq. is about to -1, the initialization worth, areas are output.
The moveto() operate is up to date with a brand new check to verify whether or not a sq. is occupied. The if-else check appears like this:
if( (r<0 || r>=SIZE) || (c<0 || c>=SIZE) )
{
m[x] = -1;
}
else
{
m[x] = r * SIZE + c;
if( board[m[x]] > -1 )
m[x] = -1;
}
The if check inside the else block – if( board[m[x]] > -1 ) – checks a sq. to see whether or not it’s been visited. In that case, -1 is about, marking the sq. off-limits.
The movecount() operate is unchanged.
I added a brand new operate, knightmove() to relocate the knight. It comprises statements beforehand discovered within the important() operate:
int knight_move(int s)
{
int x,lowest,newpos;
int strikes[KM],subsequent[KM],tally[KM];
struct plot {
int sq.;
int rely;
} nextmove[KM];
moveto(s,strikes);
for( x=0; x<KM; x++ )
{
if( strikes[x] != -1 )
{
moveto(strikes[x],subsequent);
tally[x] = movecount(subsequent);
}
else
{
tally[x] = strikes[x];
}
}
for( x=0; x<KM; x++ )
{
nextmove[x].sq. = strikes[x];
nextmove[x].rely = tally[x];
}
lowest = 8;
for( x=0; x<KM; x++ )
{
if( nextmove[x].rely<lowest && nextmove[x].rely!=-1 )
{
lowest = nextmove[x].rely;
newpos = nextmove[x].sq.;
}
}
return(newpos);
}
This new operate accomplishes three duties:
First, it builds the subsequent[] and tally[] arrays to plot the knight’s subsequent transfer.
Second, it builds a construction to retailer potential strikes, which is sorted.
Third, it returns the specified sq. to maneuver to, the one with the bottom rely of succeeding strikes (Warnsdorff’s rule). No particular resolution is made when two squares have the identical worth.
The up to date important() operate initializes the board[] array, randomly units the knight’s beginning location, then makes use of a for loop to course of all 64 squares:
for( x=0; x<SIZE*SIZE; x++ )
{
board = x;
c = knight_move(c);
chess_board();
getchar();
}
No recursion is used, as apparently my implementation of Warnsdorff’s rule is enough to whisk the knight across the chessboard.
Click on right here to view the total code on GitHub. As I wrote earlier, I’m not pleased with the code because it appears clunky to me. I attempted to hone it additional, making it extra elegant. Alas, primarily based on my method a extra poetic model of this system is past my attain.
Even so, I used to be in a position to run the code on completely different measurement chessboards and, sure, it nonetheless works. I attempted a 5-sided chessboard and a 12-sided chessboard. Due to Warnsdorff’s rule, the code correctly propels the knight across the board, by no means hitting the identical sq. twice.
It’s been many years that I’ve identified about this drawback. I’m delighted that I’ve solved it. I’d nonetheless prefer to discover the Knight’s Tour idea, which I could return to sometime. For now, it was enjoyable.
