The knight\'s tour problem is as follows: given an initial position for a single
ID: 3554133 • Letter: T
Question
The knight's tour problem is as follows: given an initial position for a
single knight on an otherwise empty chessboard, find a sequence of 64 moves that will
make the knight visit every square on the board exactly once. This seemly impossible
task can be accomplished using Warnsdorff's rule: at any time, with the knight at a given
position, there are at most eight positions on the board to which the knight could move.
Some are off the board; others have been visited earlier in the tour. Choose the position
that has the fewest open positions available to it. If this criterion yields a tie, use the
same criterion on each of the positions available from the current one, i.e., use a
second-level tie-breaker. If there's a tie at the second level, choose arbitrarily.
Write a program that will read in the starting position of the knight and produce a knight's tour beginning at that position. Is a knight's tour always possible, regardless of
the starting position?
Explanation / Answer
#include<stdio.h>
#define N 8
int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[],
int yMove[]);
/* A utility function to check if i,j are valid indexes for N*N chessboard */
int isSafe(int x, int y, int sol[N][N])
{
if ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1)
return 1;
return 0;
}
/* A utility function 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++)
printf(" %2d ", sol[x][y]);
printf(" ");
}
}
/* This function solves the Knight Tour problem using Backtracking. This
function mainly uses solveKTUtil() to solve the problem. It returns false if
no complete tour is possible, otherwise return true and prints the tour.
Please note that there may be more than one solutions, this function
prints one of the feasible solutions. */
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 solveKTUtil() */
if(solveKTUtil(0, 0, 1, sol, xMove, yMove) == false)
{
printf("Solution does not exist");
return false;
}
else
printSolution(sol);
return true;
}
/* A recursive utility function to solve Knight Tour 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;
/* 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 (solveKTUtil(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 functions */
int main()
{
solveKT();
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.