Rat in a Maze Problem

It is one of the most asked Backtracking interview questions. You will hear different names of this question like Shortest Path in a maze, Total steps in the path to reach a destination, etc. The problem statement is, we are given an N*N matrix of binary value blocks where the source cell is the upper left most block and the destination block is the lower rightmost block. The Rat can only move in two directions as forward and downward.

If the block number is 0 then it means it is a dead block (No entry) and the rat cannot visit there. If the block value is 1 then it is a valid block. So the question asks you to find that is there any way to reach the destination and find the path and print it.

Input and Output Format

Given N as input denoting the number of rows and number of columns. And from second like we N rows with N space-separated digits which form N*N Grid. You take it to return True if there exists a path to reach from source cell to destination using valid cells. Otherwise, return False if no such path exists.

Example ~

Observe the below image where Gray represents cell is dead and white says of a cell is a valid path. This is a given Grid as an input.

Rat in a Maze Problem using Backtracking in Python — Input image for Rat in a maze

We can observe that one path exists to reach the destination. The below diagram highlights the path to reach a destination.

Backtracking Approach

Using recursion we will start from the initial position of the rat and check-in right and down direction both that is it the safe path to move forward. If the path is valid then we move forward and again check for both directions recursively. whichever path gives us the solution that if we reach destination then return. Otherwise, we reach out to dead-end before reaching destination then we backtrack and start exploring another path. Let’s see the step-by-step approach to an algorithm.

First, we have the main function that accepts the maze(matrix), and the source position of the rat in a maze.
we create an empty matrix solution to store the path filled with 0's.
Create a recursive function that accepts the initial matrix, rat position coordinates, solution matrix, and length of a matrix.
Our base case is if we reach the destination then we have received one valid path.
We check whether the current position is valid or not. If it is valid then check is it already part of the solution matrix.
Otherwise, add the path in the solution matrix and explore other paths in both the forward and downward directions using recursion.
If any path is not valid then backtrack and explore other paths.

Code — Let’s implement the algorithm using Python. I will request to try implementing it first after understanding the approach.

2) The N-Queens Puzzle Problem

You have heard of this problem somewhere. The name of problems differs on different competitive sites like some will ask N-Queens problem to return any solution, N-queens problem to return all possible solution. It is the most popular and interesting problem asked in different interviews, coding rounds, etc. The problem statement is you are given an N*N matrix (Square chessboard), and your task is to find all the possible ways that you can place N number of queens on that board such that no two queens can attack each other.

Chance of Two Queens attacking each-other

If two queens are placed in the same Row.
If the two queens are placed in the same column.
If the two queens are placed in the same Diagonal.

Initially, we have a board of N*N which has all the values as 0. Now we have to find the feasible place of Queens and change 0 to 1 and if you can place N queens in N*N then return the solution.

Example

Read the approach and its implementation at the crazy-techie article through this link where you will get a complete idea of solving the problem in depth.

3) Sudoku Solver

A very similar problem which we have solved above. If you have played Sudoku on your phones then you know the game how to solve it. So Given a 9*9 matrix in which some cells are filled with numbers between 1–9 and some cells are empty(denoted by 0). You need to find a way to fill the empty cells with some digits (between 1–9) such that the final matrix represents a valid sudoku solution. The question is also asked like whether there exists a solution to solve this puzzle. If yes then return True Otherwise return False.

A sudoku solution is valid if it satisfies the following conditions

In each row, all unique digits should be there (digits between 1–9 occur only once)
In each column, unique digits should be there (digits between 1–9 occur only once)
Each of digits 1–9 must occur exactly once in each of the 9, 3*3 sub-matrices of a matrix.

Read the Backtracking approach and its implementation in python here.

End Notes

We have solved the most popular three Backtracking problems in this blog. There are many more problems in backtracking that I wanted to cover but keeping the article as short and easy to grab for you I want to end here and remaining some questions I will take in the next article. And then you will easily be able to cover all the recursion and backtracking problems at any competitive site including HackerEarth, Leetcode, HackerRank, etc.

I hope that it was easy to understand the approach of all three problems and you can implement any other problem based on a similar kind of approach. If you have any doubts then feel free to post in the comment section below or post them in a contact form.

Popular Backtracking Problems Explained Easily using Python

Table of Contents