fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. #define N 8
  5.  
  6. //possible moves
  7. int rowMove[] = {2,1,-1,-2,-2,-1,1,2};
  8. int colMove[] = {1,2,2,1,-1,-2,-2,-1};
  9.  
  10.  
  11. void printBoard(const vector<vector<int>> &visited)
  12. {
  13.     for(int i=0; i<N; i++)
  14.     {
  15.         for(int j=0;j<N;j++)
  16.             cout<<visited[i][j]<<" ";
  17.         cout<<endl;
  18.     }
  19.     cout<<endl;
  20. }
  21.  
  22. //check if the given move is valid
  23. bool isValid(const vector<vector<int>> &visited,int row, int col)
  24. {
  25.     return (row>=0 && row<N && col>=0 && col<N && visited[row][col]==0);
  26. }
  27.  
  28.  
  29. bool solveKnight(vector<vector<int>> &visited,int row, int col,int move)
  30. {
  31.     //printBoard(visited);
  32.     if(move==N*N)
  33.     {
  34.         printBoard(visited);
  35.         return true;
  36.     }
  37.  
  38.     else
  39.     {
  40.         for(int i=0;i<8;i++)
  41.         {
  42.             int newRow = row + rowMove[i];
  43.             int newCol = col + colMove[i];
  44.  
  45.             if(isValid(visited,newRow,newCol))
  46.             {
  47.                 move++;
  48.                 visited[newRow][newCol] = move;
  49.                 if(solveKnight(visited,newRow,newCol,move))
  50.                     return true;
  51.                 move--;
  52.                 visited[newRow][newCol]=0;
  53.             }
  54.         }
  55.     }
  56.     return false;
  57. }
  58.  
  59.  
  60. int main()
  61. {
  62.     vector<vector<int>> visited(N,vector<int>(N,0));
  63.     visited[0][0]=1;
  64.     if(!solveKnight(visited,0,0,1))
  65.         cout<<"not possible";
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.16s 4568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 60 39 34 31 18 9 64 
38 35 32 61 10 63 30 17 
59 2 37 40 33 28 19 8 
36 49 42 27 62 11 16 29 
43 58 3 50 41 24 7 20 
48 51 46 55 26 21 12 15 
57 44 53 4 23 14 25 6 
52 47 56 45 54 5 22 13
https://ideone.com/K0DU3q
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!