(Knight\'s tour) This chapter described the backtracking algorithm and how to us

Question

(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 chess board exactly once. For example, for a 5 times 5 and 6 times 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 once. that visits each square of the board exactly once.

Explanation / Answer

Following is the java implementation of the above problem

Please Provide your feedback if the answer is helpful

================================================

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

class Knight {
   static int N = 8;

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

     //Intialize 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[] define 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);
     }
   
   //to print 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();
         }
     }

    /* A 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;
    }

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

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.