fork(1) download 
  1.  
  2. /**
  3.  * Knights Tour
  4.  * @author PRATEEK
  5.  */
  6. class KnightTour {
  7.  
  8. 	private static int count=0 ;
  9. 	private static final int BLANK = -1;
  10. 	private static int rowLen;
  11. 	private static int colLen;
  12.  
  13. 	public static void main(String[] args) {
  14.  
  15. 		int[][] board = {
  16. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  17. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  18. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  19. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  20.  
  21. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  22. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  23. 				{-1, -1, -1,-1,   -1, -1,  -1, -1},
  24. 				{-1, -1, -1,-1,   -1, -1,  -1, -1}
  25. 		};
  26.  
  27. 		rowLen = board.length;
  28. 		colLen = board[0].length;
  29. 		knightTour(board, 0, 0, 0);
  30. 	}
  31.  
  32.  
  33. 	/**
  34. 	 * Recursive Sub-routine for Knight's Tour
  35. 	 */
  36. 	private static void knightTour(int[][] board, int row , int col , int curr)
  37. 	{
  38. 		count++;
  39. 			if(isValid(board,row,col))
  40. 			{
  41. 				board[row][col]=curr;
  42.  
  43. 				if(curr == (rowLen * colLen - 1))
  44. 				{
  45. 					printSol(board);
  46. 					System.exit(0);
  47. 				}
  48. 				else
  49. 				{
  50. 					knightTour(board,row + 2 , col + 1, curr+1 );
  51. 					knightTour(board,row + 1 , col + 2, curr+1 );
  52.  
  53. 					knightTour(board,row - 1 , col + 2, curr+1 );
  54. 					knightTour(board,row - 2 , col + 1, curr+1 );
  55.  
  56. 					knightTour(board,row - 2 , col - 1, curr+1 );
  57. 					knightTour(board,row - 1 , col - 2, curr+1 );
  58.  
  59. 					knightTour(board,row + 1 , col - 2, curr+1 );
  60. 					knightTour(board,row + 2 , col - 1, curr+1 );
  61.  
  62. 					board[row][col]=BLANK;
  63. 				}
  64. 			}
  65. 	}
  66.  
  67. 	/**
  68. 	 * Checks if for given row and col, the move is Valid or not
  69. 	 * @return true: Valid Mode, false: Invalid Move
  70. 	 */
  71. 	private static boolean isValid(int[][] board, int row, int col) {
  72. 		if(row >= 0 && row < colLen && col>=0 && col < rowLen && board[row][col]==BLANK)
  73. 			return true;
  74. 		return false;
  75. 	}
  76.  
  77. 	/**
  78. 	 * Prints the Chessboard having the hops
  79. 	 * @param board
  80. 	 */
  81. 	private static void printSol(int[][] board) {
  82. 		for(int i=0;i<colLen;i++)
  83. 		{
  84. 			for(int j=0;j<rowLen;j++)
  85. 			{
  86. 				System.out.print(board[i][j]+ "\t");
  87. 			}
  88. 			System.out.println();
  89. 		}
  90. 		System.out.println("recursive Function called " + count + " times");
  91. 	}
  92. }
  93.  
Success #stdin #stdout 0.9s 381184KB
comments (?)
stdin 
Standard input is empty
stdout 
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	
recursive Function called 66005602 times
https://ideone.com/xBd81s
Knight's Tour
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!