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:
Finding Max/Min of a List or Collection
Unsatisfied Dependency in Spring
Vector trong Java
Ép kiểu trong Java (Type casting)
Java Program to Implement Sieve Of Atkin
Java Program to Implement JobStateReasons API
Spring WebClient Requests with Parameters
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Auditing with JPA, Hibernate, and Spring Data JPA
Spring Boot - Unit Test Cases
Guide to UUID in Java
An Intro to Spring Cloud Task
Java Program to Implement Caesar Cypher
How to Get a Name of a Method Being Executed?
Autoboxing và Unboxing trong Java
Hướng dẫn Java Design Pattern – Service Locator
Java Program to Find the Longest Path in a DAG
Java Program to Implement Sorted Singly Linked List
Enum trong java
JUnit 5 @Test Annotation
Java Multi-line String
Login For a Spring Web App – Error Handling and Localization
Java Program to Implement Self Balancing Binary Search Tree
Java Program to Perform Partition of an Integer in All Possible Ways
Spring Boot - Hystrix
Guide to @JsonFormat in Jackson
Stack Memory and Heap Space in Java
Toán tử trong java
Static Content in Spring WebFlux
Jackson JSON Views
Java Program to Implement Gaussian Elimination Algorithm
Ways to Iterate Over a List in Java