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:
How to Read a File in Java
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Configuring a DataSource Programmatically in Spring Boot
Java Program to implement Circular Buffer
Collection trong java
New Features in Java 11
A Guide to TreeMap in Java
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Tiêu chuẩn coding trong Java (Coding Standards)
Java Program to Implement Min Hash
Java Program to Search for an Element in a Binary Search Tree
Java Program to implement Dynamic Array
Spring Data Reactive Repositories with MongoDB
Spring Boot - Flyway Database
A Guide to JUnit 5 Extensions
Creating a Generic Array in Java
Spring Boot - Creating Docker Image
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement Horner Algorithm
Java Deep Learning Essentials - Yusuke Sugomori
Compare Two JSON Objects with Jackson
Java Program to Implement Stack using Linked List
Spring RestTemplate Request/Response Logging
Check If a File or Directory Exists in Java
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Lấy ngày giờ hiện tại trong Java
Ignore Null Fields with Jackson
Setting Up Swagger 2 with a Spring REST API
Guide to @ConfigurationProperties in Spring Boot
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
How to Count Duplicate Elements in Arraylist
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x