Knight's Tour

Problem Statement:
      Find the sequences of the Knight on a chess board, such that Knight visits every square only once.

Fig: Knight's Tour on 5x5 Board

Download Source Code
Solution:

Knight's tour problem dates back to 9th Century AD, the procedure for completing Knight's tour was first described by Warnsdorff in 1823.

The optimal approach for solving this problem is using back-tracking.
Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

Below is the figure demonstrating the possible moves of Knight placed a given square.

Fig: Possible Moves

Below is the implementation of the logic used in the problem with Back-tracking approach.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

/** * Recursive Sub-routine for Knight's Tour */ private static void knightTour(int[][] board, int row , int col , int curr) { count++; if(isValid(board,row,col)) { board[row][col]=curr; if(curr == (rowLen * colLen - 1)) { printSol(board); System.exit(0); } else { // All Coordinates from given (row,col) knightTour(board,row + 2 , col + 1, curr+1 ); knightTour(board,row + 1 , col + 2, curr+1 ); knightTour(board,row - 1 , col + 2, curr+1 ); knightTour(board,row - 2 , col + 1, curr+1 ); knightTour(board,row - 2 , col - 1, curr+1 ); knightTour(board,row - 1 , col - 2, curr+1 ); knightTour(board,row + 1 , col - 2, curr+1 ); knightTour(board,row + 2 , col - 1, curr+1 ); board[row][col]=BLANK; } } } /** * Checks if for given row and col, the move is Valid or not * @return true: Valid Mode, false: Invalid Move */ private static boolean isValid(int[][] board, int row, int col) { if(row >= 0 && row < colLen && col>=0 && col < rowLen && board[row][col]==BLANK) return true; return false; } /** * Prints the Chessboard having the hops * @param board */ private static void printSol(int[][] board) { for(int i=0;i<colLen;i++) { for(int j=0;j<rowLen;j++) { System.out.print(board[i][j]+ "\t"); } System.out.println(); } System.out.println("recursive Function called " + count + " times"); }

Note: the order in which coordinates are given , gives the least number of  failed back-track-paths.

Please post your comments and feedback
Happy Coding !! :)