Introduction
The most popular chess game programming problem! Even if you haven’t played chess lets make this easy and simple to understand. This Knight’s tour problem defines that if it is possible to travel all the possible blocks of chess from the starting position of the chessboard.
To be clear a Knight can move only in eight specific directions/blocks from its current location. Now let’s get playing with the problem starting with some pre-requisites. Backtracking is basically recursion with undoing the recursive step if a solution for the given path does not exist.
Recursion
The most common programming paradigm is called recursion. In this algorithm we recur back again and again i.e. we call onto the same function possibly with different parameter values to recur over our problem. It mainly consists of a base condition to terminate the calls and a main recursive call part to recurring over the problem. Let us see a quick example.
Traversing a matrix of size 4 x 4 recursively:
Code implementation:
#include <bits/stdc++.h>
using namespace std;
//simple travelling that works for square matrix
void recur_travel(int mat[4][4],int row,int col,int n){
if(row == n && col == n)
return; // base condition
mat[row][col] = 1; //marking visited cells
recur_travel(mat,row+1,col+1,n); //resursion travels to row+1, col+1
//if the matrix is not square this will fail and end up in memory error as
//the stack will keep on building and never have the base condition
//p.s. just for explaination
}
int main() {
// your code goes here
int mat[4][4];
memset(mat,0,sizeof(mat));
recur_travel(mat,0,0,4); //calling recur function
//print the path matrix
for(int i = 0;i<4;i++)
{
for(int j = 0;j<4;j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
return 0;
}
Recursion always uses a recursive stack to make the function calls so evidently recursion will always have an O(n) space complexity to start with. Now when we have revised our recursion prerequisite let us dive into the problem and understand what’s happening in it. Knight tour problem is the classic backtracking problem which asks if the Knight can travel all the cells in the chessboard starting at the left top cell position.
34+ registered 
