The knight\'s tour problem is the mathematical problem of finding a knight\'s to
ID: 3817015 • Letter: T
Question
The knight's tour problem is the mathematical problem of finding a knight's tour. Create a program to find a knight's tour. Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 × 8, as well as irregular (non-rectangular) boards. Please code this in java and C. thank you.
approach this problem with the Brute Force Alogirthm.
That there are N factorial possible solutions the with the outpout conditions.
Representing a node in a virtual neural network to correspond to each square. Connected to neighboring nodes that represent legal knight moves. Predicating a next move for the knight to the nearest solution. Finding all solutions in this method would be using Brute Force approach.
Explanation / Answer
A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. The exact number of open tours on an 8×8 chessboard is still unknown.0
// C program for Knight Tour problem
#include<stdio.h>
struct figure {
int x, y, mov, movAvail[8];
struct figure *prev;
};
typedef struct figure list;
int main() {
<...>
setupKnight (&knight, x, y, board, n);
while (knight && !boardIsFull (board, n)) {
nextMove (&knight, board, n);
}
if (boardIsFull (board, n)) {
printBoard (board, n);
} else printf("No solution found.");
// Let's remove the knight
for (i = 0; i < n*n; i++) {
if (knight) {
temp = knight;
knight = temp->prev;
free(temp);
}
}
}
void setupKnight (list **knight, int x, int y, int **board, int n) {
int i;
(*knight) = malloc (sizeof(list));
(*knight)->x = x;
(*knight)->y = y;
(*knight)->mov = 1;
(*knight)->prev = NULL;
board[x][y] = 1;
for (i = 0; i < 8; i++)
(*knight)->movAvail[i] = 1;
}
int main(){
int moveIsValid (int **board, int n, int x, int y, int mov) {
if ((x < 0) || (x >= n) || (y < 0) || (y >= n)) {
return FALSE;
}
if ((board[x][y] != 0) && (board[x][y] < mov)) {
return FALSE;
}
return TRUE;
}
int nextMove (list **knight, int **board, int n) {
if ((*knight)->mov == n*n)
return FINISHED;
int x = (*knight)->x;
int y = (*knight)->y;
int mov = (*knight)->mov;
list *temp = NULL;
mov++;
if (moveIsValid(board, n, (x+1), (y+2), mov) && ((*knight)->movAvail[0] != 0)) {
(*knight)->movAvail[0] = 0;
x+=1;
y+=2;
} else
if (moveIsValid(board, n, (x+2), (y+1), mov) && ((*knight)->movAvail[1] != 0)) {
(*knight)->movAvail[1] = 0;
x+=2;
y+=1;
} else
if (moveIsValid(board, n, (x+2), (y-1), mov) && ((*knight)->movAvail[2] != 0)) {
(*knight)->movAvail[2] = 0;
x+=2;
y-=1;
} else
if (moveIsValid(board, n, (x+1), (y-2), mov) && ((*knight)->movAvail[3] != 0)) {
(*knight)->movAvail[3] = 0;
x+=1;
y-=2;
} else
if (moveIsValid(board, n, (x-1), (y-2), mov) && ((*knight)->movAvail[4] != 0)) {
(*knight)->movAvail[4] = 0;
x-=1;
y-=2;
} else
if (moveIsValid(board, n, (x-2), (y-1), mov) && ((*knight)->movAvail[5] != 0)) {
(*knight)->movAvail[5] = 0;
x-=2;
y-=1;
} else
if (moveIsValid(board, n, (x-2), (y+1), mov) && ((*knight)->movAvail[6] != 0)) {
(*knight)->movAvail[6] = 0;
x-=2;
y+=1;
} else
if (moveIsValid(board, n, (x-1), (y+2), mov) && ((*knight)->movAvail[7] != 0)) {
(*knight)->movAvail[7] = 0;
x-=1;
y+=2;
} else {
board[x][y] = 0;
if ((*knight)->prev) {
temp = (*knight);
(*knight) = (*knight)->prev;
free(temp);
mov--;
return FALSE;
}
free((*knight));
(*knight) = NULL;
return FALSE;
}
int i;
temp = malloc(sizeof(list));
board[x][y] = mov;
for (i = 0; i < 8; i++)
temp->movAvail[i] = 1;
temp->x = x;
temp->y = y;
temp->mov = mov;
temp->prev = *knight;
(*knight) = temp;
return TRUE;
}
//Java program for Knight tour problem
public class KnightTour
{
private static final int N = 8;
private int soln[][];
public KnightTour()
{
soln = new int[N][N];
}
private boolean isSafe(int x, int y)
{
if (x >= 0 && x < N && y >= 0 && y < N && soln[x][y] == -1)
return true;
return false;
}
private void printSolution()
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
System.out.print(" " + soln[x][y]);
}
System.out.println();
}
}
private boolean solveKTUtil(int x, int y, int movei, int xMove[],int yMove[])
{
int k, next_x, next_y;
if (movei == N * N)
return true;
for (k = 0; k < N; k++)
{
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y))
{
soln[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei + 1, xMove, yMove))
return true;
else
soln[next_x][next_y] = -1;
}
}
return false;
}
public boolean solveKnightTour()
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
soln[x][y] = -1;
}
}
int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
soln[0][0] = 0;
if (!solveKTUtil(0, 0, 1, xMove, yMove))
{
System.out.println("the solution does not exist");
return false;
}
else
{
printSolution();
}
return true;
}
public static void main(String... arg)
{
KnightTour knightTour = new KnightTour();
System.out.println("the solution is");
knightTour.solveKnightTour();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.