fork download
copy 
  1. // C program for Knight Tour problem
  2. #include<stdio.h>
  3. #include<iostream>
  4. using namespace std;
  5. #define N 8
  6.  
  7. int solveKTUtil(int x, int y, int movei, int sol[N][N],
  8. 				int xMove[], int yMove[]);
  9.  
  10. /* A utility function to check if i,j are valid indexes
  11. for N*N chessboard */
  12. bool isSafe(int x, int y, int sol[N][N])
  13. {
  14. 	return ( x >= 0 && x < N && y >= 0 &&
  15. 			y < N && sol[x][y] == -1);
  16. }
  17.  
  18. /* A utility function to print solution matrix sol[N][N] */
  19. void printSolution(int sol[N][N])
  20. {
  21. 	for (int x = 0; x < N; x++)
  22. 	{
  23. 		for (int y = 0; y < N; y++)
  24. 			printf(" %2d ", sol[x][y]);
  25. 		printf("\n");
  26. 	}
  27. }
  28.  
  29. /* This function solves the Knight Tour problem using
  30. Backtracking. This function mainly uses solveKTUtil()
  31. to solve the problem. It returns false if no complete
  32. tour is possible, otherwise return true and prints the
  33. tour.
  34. Please note that there may be more than one solutions,
  35. this function prints one of the feasible solutions. */
  36. bool solveKT()
  37. {
  38. 	int sol[N][N];
  39.  
  40. 	/* Initialization of solution matrix */
  41. 	for (int x = 0; x < N; x++)
  42. 		for (int y = 0; y < N; y++)
  43. 			sol[x][y] = -1;
  44.  
  45. 	/* xMove[] and yMove[] define next move of Knight.
  46. 	xMove[] is for next value of x coordinate
  47. 	yMove[] is for next value of y coordinate */
  48. 	int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  49. 	int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  50.  
  51. 	// Since the Knight is initially at the first block
  52.  
  53.  
  54. 	/* Start from 0,0 and explore all tours using
  55. 	solveKTUtil() */
  56. 	if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false)
  57.  
  58. 	{
  59. 				printSolution(sol);
  60.  
  61. 		printf("Solution does not exist");
  62. 		return false;
  63. 	}
  64. 	else
  65. 		printSolution(sol);
  66.  
  67. 	return true;
  68. }
  69.  
  70. /* A recursive utility function to solve Knight Tour
  71. problem */
  72. int solveKTUtil(int x, int y, int movei, int sol[N][N],
  73. 				int xMove[N], int yMove[N])
  74. {
  75. int k, next_x, next_y;
  76. if (movei == N*N)
  77. 	return true;
  78.  
  79. /* Try all next moves from the current coordinate x, y */
  80.  
  81. 	if (isSafe(x, y, sol))
  82. 	{
  83. 		sol[x][y]= movei;
  84. 		for (k = 0; k < 8; k++)
  85. 		{
  86. 			//cout<<sol[x][y]<<" " ;
  87. 			next_x = x + xMove[k];
  88. 			next_y = y + yMove[k];
  89. 			if (solveKTUtil(next_x, next_y, movei+1, sol,
  90. 						xMove, yMove) == true)
  91.  
  92. 			return true;
  93. 		sol[x][y] = -1;
  94.  
  95. 		}
  96.  
  97. 	// backtracking
  98.  
  99. 	return false;
  100.  
  101. 	}
  102. 	return false;
  103.  
  104. }
  105.  
  106. /* Driver program to test above functions */
  107. int main()
  108. {
  109. 	solveKT();
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1   2  -1  -1  -1  -1  17  -1 
 -1  -1  -1  -1  -1  19  12  -1 
 -1  -1   3  -1  -1  14   7  -1 
 -1  -1  -1  -1  -1   9  20  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  63
https://ideone.com/rwUUpJ
language:
C++ (gcc 8.3)
created:
6 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!