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:
Introduction to Spring Data MongoDB
Spring Security 5 for Reactive Applications
Java Program to do a Depth First Search/Traversal on a graph non-recursively
ExecutorService – Waiting for Threads to Finish
Serverless Functions with Spring Cloud Function
Spring Data Java 8 Support
Exploring the Spring Boot TestRestTemplate
Java Program to Implement Expression Tree
Java Byte Array to InputStream
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Generate N Number of Passwords of Length M Each
Guide to java.util.concurrent.Future
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
The HttpMediaTypeNotAcceptableException in Spring MVC
Spring Boot - Admin Server
Filtering a Stream of Optionals in Java
Mảng (Array) trong Java
A Quick Guide to Spring Cloud Consul
Java Program to Implement Horner Algorithm
A Guide to the ResourceBundle
Adding Parameters to HttpClient Requests
Java Program to Find a Good Feedback Vertex Set
Guide to the ConcurrentSkipListMap
Guide to the Volatile Keyword in Java
Different Ways to Capture Java Heap Dumps
How to Return 404 with Spring WebFlux
SOAP Web service: Upload và Download file sử dụng MTOM trong JAX-WS
Using a Mutex Object in Java
Deque và ArrayDeque trong Java
The DAO with Spring and Hibernate
Java – Reader to InputStream
Java – Convert File to InputStream