**Problem :- **

Solve the **Knight's tour** problem i.e find a **Knight's tour** on a **8 x 8** chessboard.

A **Knight's tour** is a sequence of moves of Knight on a chessboard such that the knight visits every square exactly once.

**Solution :- **

A **Knight** is placed on the first cell of an empty chessboard and can move according to the chess rules.

At any point on the chessboard, the knight have a maximum of **8** possible options to make a move.

**1 )** Suppose, the knight is currently in **cell ( x , y )** and it chooses one of the possible moves to a cell ( if the cell is not visited previously and the
move is indeed a valid one ). Then, we move the knight to that cell and check recursively whether we can find a solution from that
cell. If the solution exists, then that cell is marked as visited and then again knight chooses one of the possible moves and follows
same steps.

**2 )** If the solution doesn't exits, then the knight **backtracks** to the previous **cell ( x , y )** and tries out
other possible alternatives.

When all the cells are visited, we have found a sequence of knight moves which visits every cell on the chessboard exactly once.
See the implementation below.

**#include<iostream>
#define N 8**
**using namespace** std;
*// defines a structure for chess moves*
**typedef struct** chess_moves {
*// 'x' and 'y' coordinates on chess board*
**int** x,y;
}chess_moves;
*// displays the knight tour solution*
**void** printTour(**int** tour[N][N]) {
**int** i,j;
**for** (i = 0; i < N; i++) {
**for** (j = 0; j < N; j++) {
cout<<tour[i][j]<<"\t";
}
cout<<endl;
}
}
*// check if the next move (as per knight's constraints) is possible*
**bool** isMovePossible(chess_moves next_move, **int** tour[N][N]) {
**int** i = next_move.x;
**int** j = next_move.y;
**if** ((i >= 0 && i < N) && (j >= 0 && j < N) && (tour[i][j] == 0))
**return true**;
**return false**;
}
*// recursive function to find a knight tour*
**bool** findTour(**int** tour[N][N], chess_moves move_KT[],
chess_moves curr_move, **int** move_count) {
**int** i;
chess_moves next_move;
**if** (move_count == N*N-1) {
*// Knight tour is completed i.e all cells on the
// chess board has been visited by knight once *
**return true**;
}
*// try out the possible moves starting from the current coordinate*
**for** (i = 0; i < N; i++) {
*// get the next move*
next_move.x = curr_move.x + move_KT[i].x;
next_move.y = curr_move.y + move_KT[i].y;
**if** (isMovePossible(next_move, tour)) {
*// if the move is possible
// increment the move count and store it in tour matrix*
tour[next_move.x][next_move.y] = move_count+1;
**if** (findTour(tour, move_KT, next_move, move_count+1) == **true**) {
**return true**;
}
**else** {
*// this move was invalid, try out other possiblities *
tour[next_move.x][next_move.y] = 0;
}
}
}
**return false**;
}
*// wrapper function*
**void** knightTour() {
**int** tour[N][N];
**int** i,j;
*// initialize tour matrix*
**for** (i = 0; i < N; i++) {
**for** (j = 0; j < N; j++) {
tour[i][j] = 0;
}
}
*// all possible moves that knight can take*
chess_moves move_KT[8] = { {2,1},{1,2},{-1,2},{-2,1},
{-2,-1},{-1,-2},{1,-2},{2,-1} };
*// knight tour starts from coordinate (0,0)*
chess_moves curr_move = {0,0};
*// find a possible knight tour using a recursive function
// starting from current move *
**if**(findTour(tour, move_KT, curr_move, 0) == **false**) {
cout<<"\nKnight tour does not exist";
}
**else** {
cout<<"\nTour exist ...\n";
printTour(tour);
}
}
*// main*
**int** main() {
knightTour();
cout<<endl;
**return** 0;
}