Question

JAVA code:

(Knight’s tour)This chapter described the backtracking algorithm and how to use recursion to implement it.Another well-known chessboard problem that can be solved using the backtracking algorithm is a knight’s tour.Given an initial board position, determine a sequence of moves by a knight that will visit every square of the chessboard exactly once.For example,for a 5 × 5 and 6 × 6 square board,the sequence of moves are shown in Figure 5-22.

A knight moves by jumping two positions either vertically or horizontally and one position in the perpendicular direction.Write a recursive backtracking program that takes as input an initial board position and determines a sequence of moves by a knight that visits each square of the board exactly once.

Answer 1

Java code:-

import java.util.*;
import java.io.*;

class Knight {
static int N = 8;

static boolean solutionKnightTour() {
int finalMat[][] = new int[8][8];

//Intializing matrix with -1
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
finalMat[x][y] = -1; //Solution matrix

/* aMove[] and bMove[] indicates next move of Knight.
aMove[] is for next value of x coordinate
bMove[] is for next value of y coordinate */
int aMove[] = {2, 1, -1, -2, -2, -1, 1, 2};
int bMove[] = {1, 2, 2, 1, -1, -2, -2, -1};

// Since the Knight is initially at the first block
finalMat[0][0] = 0;

/* Start from 0,0 and explore all tours using
solveKnightTourUtil() */
if (!solutionKnightTourUtil(0, 0, 1, finalMat, aMove, bMove)) {
System.out.println("Solution does not exist");
return false;
} else
printSolution(finalMat);

return true;
}

static boolean isMatSafeToUse(int a, int b, int finalMat[][]) {
return (a >= 0 && a < N && b >= 0 &&
b < N && finalMat[a][b] == -1);
}

//printing the final matrix
static void printSolution(int finalmat[][]) {
for (int a = 0; a < N; a++) {
for (int b = 0; b < N; b++)
System.out.print(finalmat[a][b] + " ");
System.out.println();
}
}

/* we use recursive utility function to solve Knight
Tour problem */
static boolean solutionKnightTourUtil(int a, int b, int movei,
int finalmat[][], int aMove[],
int bMove[]) {
int k, next_a, next_b;
if (movei == N * N)
return true;

/* Try all next moves from the current coordinate
x, y */
for (k = 0; k < 8; k++) {
next_a = a + aMove[k];
next_b = b + bMove[k];
if (isMatSafeToUse(next_a, next_b, finalmat)) {
finalmat[next_a][next_b] = movei;
if (solutionKnightTourUtil(next_a, next_b, movei + 1,
finalmat, aMove, bMove))
return true;
else
finalmat[next_a][next_b] = -1;// backtracking
}
}

return false;
}

/* main program to run above functions */
public static void main(String args[]) {
solutionKnightTour();
}
}