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:
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Generating Random Numbers in a Range in Java
Các nguyên lý thiết kế hướng đối tượng – SOLID
Java IO vs NIO
Debugging Reactive Streams in Java
Java Program to find the maximum subarray sum using Binary Search approach
Converting a List to String in Java
Check if a String is a Palindrome in Java
Hướng dẫn Java Design Pattern – State
Java Program to Implement Fermat Primality Test Algorithm
Number Formatting in Java
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Integer Constant Pool trong Java
Spring REST API with Protocol Buffers
Java Program to Implement Double Ended Queue
Spring Boot Actuator
The Spring @Controller and @RestController Annotations
Deque và ArrayDeque trong Java
Jackson Exceptions – Problems and Solutions
StringBuilder vs StringBuffer in Java
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java Program to Perform Left Rotation on a Binary Search Tree
Java Program to Implement EnumMap API
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Spring Security OAuth2 – Simple Token Revocation
Java Program to Implement Radix Sort
Java Program to Implement Triply Linked List
Spring Boot - Scheduling
Working with Network Interfaces in Java
Lớp LinkedHashMap trong Java
Java Program to Implement Min Heap
Spring 5 Testing with @EnabledIf Annotation