Exercise 8.22 on textbook pages 340 – 341 describes the Knight’s Tour problem, o
ID: 3576346 • Letter: E
Question
Exercise 8.22 on textbook pages 340 – 341 describes the Knight’s Tour problem, originally proposed by the mathematician Euler. The Knight’s Tour problem asks this question: “Can the chess piece called the knight move around an empty chessboard and visit each of the 64 squares once and only once?” Please read the textbook for a detailed description of the problem.
Exercise 8.22 (b) and (c) ask you to create two C# apps for this problem. The following is a brief description of these two parts. Please see the textbook for detailed directions and requirements of the two apps.
In part (b) you are asked to write an app to move the knight around the chessboard. The app randomly picks a square on the chessboard as the initial position of the knight. It then uses the directions described in the textbook to move the knight around until either all squares have been visited or no valid move is possible. Store the numbers 1 through 64 in the squares to indicate the sequence of moves took by the knight. For example, if the upper-left corner of the chessboard is randomly picked as the initial position of the knight, store 1 in that square (which is cell [0,0] in a two-dimensional array). If the program then moves the knight one row down and two columns to the right, store 2 in cell [1,2] in the array. If the program then moves the knight another row down and another two columns to the right, store 3 in cell [2,4] in the array. Continue this until the knight has nowhere to go.
The following is the output of a test run of the program:
The tour ended with 37 moves.
This was not a full tour.
0 1 12 37 4 9 20 7
13 36 3 10 19 6 25 22
2 11 18 5 24 21 8 27
0 14 35 30 17 26 23 0
0 31 16 0 34 0 28 0
15 0 33 0 29 0 0 0
32 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
The number in each cell of the 8 by 8 array indicates when that cell was visited by the knight. Cells with 0’s are cells that were never visited. Since the tour ended with 37 moves, we see number 1 through 37 in the cells. The following is the output of another test run of the program:
The tour ended with 45 moves.
This was not a full tour.
0 9 20 45 12 7 4 15
21 44 11 8 3 14 39 6
10 19 2 13 38 5 16 29
1 22 43 32 17 28 37 40
0 33 18 0 36 41 30 27
23 0 35 42 31 26 0 0
34 0 0 25 0 0 0 0
0 24 0 0 0 0 0 0
The tour ends with 45 moves. Most test runs will have somewhere between 30 and 50 moves.
Please submit your complete C# project for Exercise 8.22(b) to Blackboard.
Exercise 8.22(c) asks you to rewrite the program with a new algorithm. An accessibility number is assigned to each cell to indicate how accessible the cell is. In every step, compare the possible moves and move the knight to the cell with the lowest accessibility. Since this makes later moves easier, the new algorithm will end up having more moves than before.
Please read page 341 of the textbook for a detailed description of this program. The textbook tells you to pick one of the four corners as the initial position of the knight. Do not follow this direction. Instead, pick a random position anywhere in the chessboard as the initial position just like what you do in Exercise 8.22 (b).
The following is the output of a test run of the program:
The tour ended with 57 moves.
This was not a full tour.
10 7 12 27 38 5 22 25
13 28 9 6 23 26 37 4
8 11 0 39 44 51 24 21
29 14 43 50 0 36 3 52
42 49 40 45 0 0 20 35
15 30 0 0 57 0 53 2
48 41 32 17 46 55 34 19
31 16 47 56 33 18 1 54
The tour ends with 57 moves. Most test runs with this new algorithm will have 55 moves or more.
Explanation / Answer
#inlcude<iostream>
#define n 8
using namespace std;
int solveKnightUtil(int x, int y, int movei, int sol[n][n],
int xMove[], int yMove[]);
/* A utility method to check if i,j are valid indexes
for n*n chessboard */
bool isSafe(int x, int y, int sol[n][n])
{
return ( x >= 0 && x < n && y >= 0 &&
y < n && sol[x][y] == -1);
}
/* A utility method to print solution matrix sol[n][n] */
void printSolution(int sol[n][n])
{
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
Console.WriteLine( sol[x][y]);
Console.WriteLine(" ");
}
}
/* This method solves the Knight Tour problem using
Backtracking. This method mainly uses solveKnightUtil()
to solve the problem. It returns false if no complete
tour is possible, otherwise return true and prints the
tour. */
bool solveKT()
{
int sol[n][n];
/* Initialization of solution matrix */
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
sol[x][y] = -1;
/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
// Since the Knight is initially at the first block
sol[0][0] = 0;
/* Start from 0,0 and explore all tours using
solveKnightUtil() */
if (solveKnightUtil(0, 0, 1, sol, xMove, yMove) == false)
{
Console.WriteLine("Solution does not exist");
return false;
}
else
printSolution(sol);
return true;
}
/* A recursive utility method to solve Knight Tour
problem */
int solveKnightUtil(int x, int y, int movei, int sol[n][n],
int xMove[n], int yMove[n])
{
int k, next_x, next_y;
if (movei == n*n)
return true;
/* Try all next moves from the current coordinate x, y */
for (k = 0; k < 8; k++)
{
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol))
{
sol[next_x][next_y] = movei;
if (solveKnightUtil(next_x, next_y, movei+1, sol,
xMove, yMove) == true)
return true;
else
sol[next_x][next_y] = -1; //backtracking
}
}
return false;
}
/* Driver program to test above method */
public class KnightTourTest
{
static void main()
{
solveKT();
return 0;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.