The Knight’s Tour Problem [GeeksforGeeks]

Here is the detailed description of Knight's Tour problem. I use backtraking to solve this problem.

#include <iostream>
#include <iomanip>

const int W=8, H=8;

//Print solution
void printSol(int board[W][H]){
    for(int i=0; i<W; i++){
        for(int j=0; j<H; j++){
            std::cout<<std::setw(3)<<board[i][j]<< "  ";
        }
        std::cout<<std::endl;
    }
}

//Check validitiy of the current cell
bool isValid(int x, int y, int board[W][H]){
    return (0<=x && x<W && 0<=y && y<H && board[x][y]==-1);
}

//Do backtracking
bool KnightTour(int x, int y, int board[W][H], int cur){
    if(cur==W*H-1){
        board[x][y]=cur;
        return true;    
    }
    int moveX[8]={2, 1, -1, -2, -2, -1, 1, 2};
    int moveY[8]={1, 2, 2, 1, -1, -2, -2, -1};
    board[x][y]=cur;
    for(int i=0; i<8; i++){
        int a=x+moveX[i], b=y+moveY[i];
        if(isValid(a, b, board)&&KnightTour(a, b, board, cur+1))
            return true;
    }
    board[x][y]=-1;
    return false;
}

//Find Knight's Tour
int main ()
{
    int board[W][H];
    for(int i=0; i<W; i++)
        for(int j=0; j<H; j++)
            board[i][j]=-1;
    if(KnightTour(0, 0, board, 0)){
        std::cout << "The solution is:" << std::endl;
        printSol(board);
    }
    else
        std::cout << "No solution exists" << std::endl;    
    return 0;
}