Do you think IIT Guwahati certified course can help you in your career?
Problem Statement
You are given a 2D matrix of size NxN and a cell (X, Y). Suppose a knight is standing at the given cell. Your task is to find all the possible paths such that the knight must visit each cell exactly once.
We can solve this problem using recursion and backtracking. The idea is to start from the given cell and recursively iterate to the valid cells. We can use a vector or string to store the current path, and if a path is a valid path, we will store that path.
As shown in the figure, if the knight is at cell (x, y), then the cells (x-1, y+2), (x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2), (x-1, y-2), (x-2, y-1) and (x-2, y+1) can be the valid cells.
Steps To Solve
Declare a boolean variable ‘ok’ to check whether a valid path exists or not.
Make a function isValid(int x, int y, int &N, vector <vector<bool>> &vis) to check whether the given cell (x, y) is valid or not.
If x < 0 or y < 0 or x >= N or y >= N then the current cell is out of bounds so return false.
If vis[x][y] == true, then the cell (x, y) is already visited hence it is invalid so return false.
If all the above conditions are false, the cell is valid, so return true.
Make a function 'paths(int x, int y, int &N, vector <pair<int, int>> &curr, vector <vector<bool>> &vis)' to find all the valid paths from the given cell. (x, y) denotes the current cell, vector of pairs curr stores the current path and 2D boolean matrix vis is used to mark all the visited cells.
Base case: If the number of visited cells is NxN (i.e., the size of curr is NxN), print the current path and as there exists at least one path, mark ok astrue.
Iterate the direction vectors dx[] and dy[] simultaneously to generate the coordinate (newX, newY) of possible valid cells.
If it is a valid cell, then mark it visited and push the coordinate (newX, newY) to the vector curr, then recursively call the function paths(newX, newY, N, curr, vis).
Backtrack to explore other paths.
Mark the given cell (X, Y) as visited and initiate the function paths from (X, Y). If ok == false, then no valid sequence exists. so print "No valid sequence!!"
Code
#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 7;
int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
bool ok = false;
//function to check whether the given cell (x, y) is valid or not.
bool isValid(int x, int y, int &N, vector <vector<bool>> &vis){
//check bounds
if(x < 0 || y < 0 || x >= N || y >= N)
return false;
///If the cell (x, y) is already visited, return false
if(vis[x][y])
return false;
//valid cell
return true;
}
////function to find all the valid paths from the given cell
void paths(int x, int y, int &N, vector <pair<int, int>> &curr, vector <vector<bool>> &vis){
//base case
if(curr.size() == N * N){
//as there exists at least one path, mark ok as true
ok = true;
for(auto u : curr){
cout << "(" << u.first << ", " << u.second << ")" << " ";
}
cout << "\n" << "\n";
return;
}
//Iterate the direction vectors dx[] and dy[] simultaneously to generate the coordinate (newX, newY) of possible valid cells.
for(int i = 0; i < 8; ++i){
int newX = x + dx[i];
int newY = y + dy[i];
//check the new cell is valid or not
if(isValid(newX, newY, N, vis)){
//mark the cell as visited
vis[newX][newY] = true;
//update the current path
curr.push_back({newX, newY});
paths(newX, newY, N, curr, vis);
//Backtrack to explore other paths
curr.pop_back();
vis[newX][newY] = false;
}
}
}
signed main(){
int N;
cin >> N;
int X, Y;
cin >> X >> Y;
//2D boolean matrix vis to mark all the visited cells
vector <vector<bool>> vis(N, vector <bool> (M, 0));
//Mark the given cell (X, Y) as visited
vis[X][Y] = true;
//vector to store the current path
vector <pair<int, int>> curr;
curr.push_back({X, Y});
//initiate the function paths from (X, Y)
paths(X, Y, N, curr, vis);
if(!ok){
cout << "No valid sequence!!" << "\n";
}
return 0;
}
What is Backtracking? Backtracking is an algorithmic tool that recursively generates all the possible combinations to solve the given problem.
Key Takeaways
In this article, we solved a problem using recursion and backtracking. If you want to master competitive programming or prepare for coding interviews, then backtracking is one of the most important topics. Check out this coding ninjas' blog for getting a better hold on it.
To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.
Happy learning!
Live masterclass
Zomato Data Analysis Case Study: Ace 25L+ Roles in FoodTech
by Abhishek Soni
16 Mar, 2026
01:30 PM
Data Analysis for 20L+ CTC@Flipkart: End-Season Sales dataset
by Sumit Shukla
15 Mar, 2026
06:30 AM
Beginner to GenAI Engineer Roadmap for 30L+ CTC at Amazon
by Shantanu Shubham
15 Mar, 2026
08:30 AM
Multi-Agent AI Systems: Live Workshop for 25L+ CTC at Google
by Saurav Prateek
16 Mar, 2026
03:00 PM
Zomato Data Analysis Case Study: Ace 25L+ Roles in FoodTech
by Abhishek Soni
16 Mar, 2026
01:30 PM
Data Analysis for 20L+ CTC@Flipkart: End-Season Sales dataset
40+ registered 
