#include <iostream>
const int N = 8;


/* This array represents the chess board. 
We'll record the move number that takes us to a given box.*/
int visited[N][N];

/* xMove[] and yMove[] define next move of Knight. */
int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };




/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && visited[x][y] == -1;
}



/* Find accessibility*/
int findAccessibility(int x, int y) {

   // Accessibility matrix
   int access[ 8 ][ 8 ] = { { 2, 3, 4, 4, 4, 4, 3, 2 },
                            { 3, 4, 6, 6, 6, 6, 4, 3 },
                            { 4, 6, 8, 8, 8, 8, 6, 4 },
                            { 4, 6, 8, 8, 8, 8, 6, 4 },
                            { 4, 6, 8, 8, 8, 8, 6, 4 },
                            { 4, 6, 8, 8, 8, 8, 6, 4 },
                            { 3, 4, 6, 6, 6, 6, 4, 3 },
                            { 2, 3, 4, 4, 4, 4, 3, 2 } };

   int acc = access[x][y];

   // Need to reduce accessibilty as the chessboard fills in 
   for (int k = 0; k < 8; k++) {
      if( (x+xMove[k]) >=0 && (y+yMove[k]) >=0 && 
          (x+xMove[k]) < N && (y+yMove[k]) < N && 
         visited[x+xMove[k]][y+yMove[k]] != -1) acc--;
   }

   return acc;
}




/* Find coordinates of the next move that are least accessible*/
bool findLowestAccessibleMove(int x, int y, int& nextX, int& nextY) {

   // Try all next moves from the current coordinate x, y 
   int tempX, tempY, minAccess = 10, access, index =-1;

   for (int k = 0; k < 8; k++) {
      tempX = x + xMove[k];
      tempY = y + yMove[k];

      if( !(isSafe(tempX, tempY)) ) continue;
      access = findAccessibility(tempX, tempY);

      if(access < minAccess) {
         minAccess = access;
         index = k;
      }    
   }

   bool success = false;
   if(index > -1) {
      success = true;
      nextX = x + xMove[index];
      nextY = y + yMove[index];
   }

   return success;
}




/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
   std::cout << "-----------------------------------------------------------------" << std::endl;
    for (int x = 0; x < N; x++) { 
       std::cout << "|";
        for (int y = 0; y < N; y++)
           std::cout << " " << visited[x][y] << "\t| ";
        std::cout << std::endl;
    }
   std::cout << "-----------------------------------------------------------------" << std::endl;
}



/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei) {

    if (movei == N*N) return true;

    /* Try next move from the current coordinate x, y */
    int nextX, nextY;
    if( !(findLowestAccessibleMove(x, y, nextX, nextY)) ) return false; 
    visited[nextX][nextY] = movei;


    if (knightsTourRecursive(nextX, nextY, movei+1))  // recursion
       return true;
    else
       visited[nextX][nextY] = -1;             // backtracking
    

    return false;
}




/* Run Knight's Tour program starting with a given initial position */
bool knightsTour(int initX, int initY) {
    /* Initialization of solution matrix */
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            visited[x][y] = -1;

    std::cout << "Starting at " << initX << " " << initY << std::endl;

    // Since the Knight is initially at the origin
    visited[initX][initY]  = 0;

    /* explore all tours using recursion */
    if(!knightsTourRecursive(initX, initY, 1) ) {
       std::cout << "Solution does not exist" << std::endl;
        return false;
    }
    else
        printSolution();

    return true;
}





int main() {

   for (int i=0; i<8; i++) 
      for (int j=0; j<8; j++) 
         knightsTour(i, j);

   return 0;
}