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.
package com.vipin.algorithms; 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(); } }
$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
Related posts:
Comparing Two HashMaps in Java
Java Program to Represent Linear Equations in Matrix Form
Primitive Type Streams in Java 8
Java Program to implement Associate Array
Java Program to Implement Hash Tables Chaining with Binary Trees
A Guide to @RepeatedTest in Junit 5
Quick Guide to Spring Bean Scopes
Hướng dẫn Java Design Pattern – Chain of Responsibility
Java Program to Implement Skew Heap
Java Program to Implement Bubble Sort
JWT – Token-based Authentication trong Jersey 2.x
A Guide to JUnit 5
Java Program to Implement IdentityHashMap API
Từ khóa this và super trong Java
Simple Single Sign-On with Spring Security OAuth2
Java Program to Implement Vector API
Java Program to Implement Graph Coloring Algorithm
Java Program to Perform Naive String Matching
Java Program to implement Bi Directional Map
Java Program to Implement SynchronosQueue API
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Apache Tiles Integration with Spring MVC
Deque và ArrayDeque trong Java
Immutable Map Implementations in Java
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
How to Get the Last Element of a Stream in Java?
Spring Cloud AWS – S3
Chuyển đổi giữa các kiểu dữ liệu trong Java
Send an email using the SMTP protocol
Introduction to the Java NIO2 File API
Guide to the Volatile Keyword in Java
Java Program to Print only Odd Numbered Levels of a Tree