fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. using namespace std;
  4. #define N 8
  5.  
  6.  
  7.  
  8. void OutputArr(int A[N][N])
  9. {
  10.  
  11.     for(int i = 0; i < N; i++){
  12. 	for(int j = 0; j < N; j++){
  13. 		cout << A[i][j] << " ";
  14. 	}
  15. 	cout << endl;
  16. }
  17. }
  18.  
  19. // Check if the move is available
  20. int isSafe(int x, int y, int A[N][N])
  21. {
  22. 	if(x >= 0 &&
  23. 	   y >= 0 &&
  24. 	   x < N &&
  25. 	   y < N &&
  26. 	   A[x][y] == -1) // If the square is still not visited
  27. 		return 1;
  28. 	return 0;
  29. }
  30.  
  31. int BackTrack(int sol[N][N], int xMove[N], int yMove[N], int x, int y,
  32. 	int Move)
  33. {
  34. 	int k, next_x, next_y;
  35. 	if(Move == N * N){
  36. 		return true;
  37. 	}
  38.  
  39.     // Try all next moves
  40. for(k = 0; k < N; k++){
  41. 	next_x = x + xMove[k];
  42. 	next_y = y + yMove[k];
  43. 	if(isSafe(next_x, next_y, sol)){
  44. 		sol[next_x][next_y] = Move;
  45. 		if(BackTrack(sol, xMove, yMove, next_x, next_y, Move + 1) == true){
  46. 			return true;
  47. 		}
  48. 		else // Backtrack, mark that the path is fail
  49. 			sol[next_x][next_y] = -1;
  50. 	}
  51. }
  52. return false;
  53. }
  54.  
  55. bool Solve()
  56. {
  57. 	int sol[N][N];
  58.  
  59.     // Set up the "board"
  60. for(int i = 0; i < N; i++){
  61. 	for(int j = 0; j < N; j++){
  62. 		sol[i][j] = -1;
  63. 	}
  64. }
  65.  
  66. // Square that the Knight can move to
  67. int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
  68. int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
  69.  
  70. // Where the knight starts
  71. sol[0][0] = 0;
  72.  
  73. if(BackTrack(sol, xMove, yMove, 0, 0, 1) == false){
  74. 	cout << "No solution." << endl;
  75. 	return false;
  76. }
  77. else{
  78. 	OutputArr(sol);
  79. }
  80. return true;
  81. }
  82.  
  83. int main()
  84. {
  85. 	Solve();
  86.     getchar();
  87. 	return 0;
  88. }
Success #stdin #stdout 0.44s 3144KB
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
https://ideone.com/sXhZAQ
language:
C++ (gcc 8.3)
created:
9 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!