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.
Backtracking
It refers to the algorithm that works right after the recursive step i.e. if the following recursive step results in a false then it retraces back and rectifies the changes made by the following recursive function. Here in this problem of Knight tour, the knight can move the specified blocks/cells mentioned in the given row, column array:
row[8] = {2, 1, -1, -2, -2, -1, 1, 2 };
column[8] = {1, 2, 2, 1, -1, -2, -2, -1 };
Few valid steps are shown from cell I,j.
Algorithm Steps:
- Travel the matrix to only valid cells marked in the row, column array as coordinates.
- If the step is valid then mark the current move in that cell of the matrix.
- If the current cell is not valid or like it does not help in a complete traversal of the matrix then recur back and change the current value of the matrix which was updated before the recursive step.
- Recur until move equals 8 x 8 = 64 – chess board general size.
Code Implementation:
#include <bits/stdc++.h>
#define N 8
using namespace std;
int mat[N][N];
//simple travelling that works for square matrix
int row[N] = {2, 1, -1, -2, -2, -1, 1, 2 };
int col[N] = {1, 2, 2, 1, -1, -2, -2, -1 };
bool isValid(int r,int c){
return (r>=0 && c>=0 && r<N && c<N && mat[r][c] == -1);
}
bool knight_tour(int r,int c,int move){
if(move == N*N)
return true; // base condition
int move_x, move_y;
for(int k = 0;k<N;k++){
move_x = r + row[k];
move_y = c + col[k];
if(isValid(move_x,move_y)){
mat[move_x][move_y] = move + 1; //storing the move number in matrix
if(knight_tour(move_x,move_y,move + 1) == 1)return true;
else mat[move_x][move_y] = -1;//backtracking
}
}
return false;
}
int main() {
// your code goes here
memset(mat,-1,sizeof(mat));
mat[0][0] = 1;
if(knight_tour(0,0,1)){//calling recur function
//print the path matrix
for(int i = 0;i<N;i++)
{
for(int j = 0;j<N;j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
}
else cout<<"Not possible\n";
return 0;
}
Time Complexity: O(8^(NN)), as there are NN cells in the board/matrix.
Space Complexity: O(N*N), size of the board and general recursive calls are not considered in this calculation.
Now let us see one more variant of Knight Tour probability problem:
In this problem everything remains the same, the knight has to travel the matrix with valid moves, only here we have to find the probability of the knight remaining on the board after K moves. This can easily be solved by counting for each cell how many times the knight has moved to the given cell and sum them up and at last, dividing the answer by N as for each cell of a N x N matrix the probability of valid move if the move to stay there only i.e. 1/N. Note: Better to divide by the float value of N for exact answer and probability.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
double knightProbability(int N, int K, int sr, int sc) {
vector<vector<double>> dp(N, vector<double>(N));
//direction of valid moves in the matrix
vector<int> dr = {2, 2, 1, 1, -1, -1, -2, -2};
vector<int> dc = {1, -1, 2, -2, 2, -2, 1, -1};
dp[sr][sc] = 1; //marking the starting cell
for (; K > 0; K--) {
vector<vector<double>> dp2(N, vector<double>(N));
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 0; k < 8; k++) {
int cr = r + dr[k];
int cc = c + dc[k];
if (0 <= cr && cr < N && 0 <= cc && cc < N) {
dp2[cr][cc] += dp[r][c] / 8.0; //storing the probability in each cell and summing them up.
Time Complexity: O(NNK), where K is the number of moves that can be moved by the knight.
Space Complexity: O(N*N), where N is the size of the matrix/board.
Backtracking hence becomes a very powerful tool when we have to move through all the available possibility by recurring over the subproblems and if we could not reach a solution we trace back and correct it. Although the space complexity is quite high along with the time complexity but traversing through all possible options will require a definite amount of complexity than general algorithms. Hope the use of the algorithm will be easier now with the application and hope this article helps an aspiring software developer and programmer.
Check out the next article on mastering Competitive Programming.
By Aniruddha Guin
