Java Program to Implement Knight’s Tour Problem

«
»
This Java Program is to Implement Knight’s Tour Problem.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.

Here is the source code of the Java Program to Implement Knight’s Tour Problem. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. package com.vipin.algorithms;
  2.  
  3. public class KnightTour
  4. {
  5.     private static final int N = 8;
  6.     private int soln[][];
  7.  
  8.     public KnightTour()
  9.     {
  10.         soln = new int[N][N];
  11.     }
  12.  
  13.     private boolean isSafe(int x, int y)
  14.     {
  15.         if (x >= 0 && x < N && y >= 0 && y < N && soln[x][y] == -1)
  16.             return true;
  17.         return false;
  18.     }
  19.  
  20.     private void printSolution()
  21.     {
  22.         for (int x = 0; x < N; x++)
  23.         {
  24.             for (int y = 0; y < N; y++)
  25.             {
  26.                 System.out.print("  " + soln[x][y]);
  27.             }
  28.             System.out.println();
  29.         }
  30.     }
  31.  
  32.     private boolean solveKTUtil(int x, int y, int movei, int xMove[],int yMove[])
  33.     {
  34.         int k, next_x, next_y;
  35.         if (movei == N * N)
  36.             return true;
  37.  
  38.         for (k = 0; k < N; k++)
  39.         {
  40.             next_x = x + xMove[k];
  41.             next_y = y + yMove[k];
  42.             if (isSafe(next_x, next_y))
  43.             {
  44.                 soln[next_x][next_y] = movei;
  45.                 if (solveKTUtil(next_x, next_y, movei + 1, xMove, yMove))
  46.                     return true;
  47.                 else
  48.                     soln[next_x][next_y] = -1;
  49.             }
  50.         }
  51.         return false;
  52.     }
  53.  
  54.     public boolean solveKnightTour()
  55.     {
  56.         for (int x = 0; x < N; x++)
  57.         {
  58.             for (int y = 0; y < N; y++)
  59.             {
  60.                 soln[x][y] = -1;
  61.             }
  62.         }
  63.         int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  64.         int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  65.         soln[0][0] = 0;
  66.         if (!solveKTUtil(0, 0, 1, xMove, yMove))
  67.         {
  68.             System.out.println("the solution does not exist");
  69.             return false;
  70.         }
  71.         else
  72.         {
  73.             printSolution();
  74.         }
  75.         return true;
  76.     }
  77.  
  78.     public static void main(String... arg)
  79.     {
  80.         KnightTour knightTour = new KnightTour();
  81.         System.out.println("the solution is");
  82.         knightTour.solveKnightTour();
  83.     }
  84. }


advertisement
$javac KnightTour.java
$java KnightTour
the solution is
 
 0  59  38  33  30  17  8  63
 37  34  31  60  9  62  29  16
 58  1  36  39  32  27  18  7
 35  48  41  26  61  10  15  28
 42  57  2  49  40  23  6  19
 47  50  45  54  25  20  11  14
 56  43  52  3  22  13  24  5
 51  46  55  44  53  4  21  12

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.