#include <iostream>
#include <ctime>

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;
}



/* 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) {
    int nextX, nextY;

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


    /* Try all next moves from the current coordinate x, y */
    for (int k = 0; k < 8; k++) {
        nextX = x + xMove[k];
        nextY = y + yMove[k];

        if (isSafe(nextX, nextY)) {
            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() {
    srand( (unsigned) time(0));

    int initX = rand() % N;
    int initY = rand() % N;

    // Good starting points: (0,0), (0,3), (0,7), (2,6), (3,2), 
    // (4,0), (4,2), (4,5), (7,0), (7,3), (7,4) 

    knightsTour(initX, initY);

    return 0;
}