you to create C# apps for this problem. In part (b) you are asked to write an ap
ID: 3573249 • Letter: Y
Question
you to create C# apps for this problem.
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 describedin 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 anothertest 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.
Explanation / Answer
#include<stdio.h>
#define N 8
int solveKTUtil(int x, int y, int movei, int sol[N][N],
int xMove[], int yMove[]);
bool isSafe(int x, int y, int sol[N][N])
{
return ( x >= 0 && x < N && y >= 0 &&
y < N && sol[x][y] == -1);
}
void printSolution(int sol[N][N])
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
printf(" %2d ", sol[x][y]);
printf(" ");
}
}
bool solveKT()
{
int sol[N][N];
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
sol[0][0] = 0;
if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false)
{
printf("Solution does not exist");
return false;
}
else
printSolution(sol);
return true;
}
problem */
int solveKTUtil(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;
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 (solveKTUtil(next_x, next_y, movei+1, sol,
xMove, yMove) == true)
return true;
else
sol[next_x][next_y] = -1;// backtracking
}
}
return false;
}
int main()
{
solveKT();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.