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:
Upload and Display Excel Files with Spring MVC
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
OAuth2.0 and Dynamic Client Registration
Java Program to Implement Stack using Two Queues
How to Add a Single Element to a Stream
Java Program to Perform Searching Using Self-Organizing Lists
Guide to the Java ArrayList
Java Collections Interview Questions
Từ khóa this và super trong Java
Tổng quan về ngôn ngữ lập trình java
An Introduction to ThreadLocal in Java
Java 8 and Infinite Streams
@DynamicUpdate with Spring Data JPA
Command-Line Arguments in Java
Check If a String Is Numeric in Java
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
Primitive Type Streams in Java 8
Từ khóa throw và throws trong Java
Array to String Conversions
Collect a Java Stream to an Immutable Collection
Java Program to Implement JobStateReasons API
@Lookup Annotation in Spring
Java Program to Compute the Area of a Triangle Using Determinants
Convert char to String in Java
Set Interface trong Java
Java Program to Implement Self Balancing Binary Search Tree
ArrayList trong java
Spring Security Registration – Resend Verification Email
Java Program to Check if a Matrix is Invertible
Java Program to Check Whether an Undirected Graph Contains a Eulerian Cycle
Spring Boot with Multiple SQL Import Files