Hello and welcome, Hope you are fine. In our previous article of competitive programming series, we have started Backtracking and have studied all the basics of backtracking and have also solved 2 coding questions of Backtracking. In this article, we will continue the series and will pick some medium and hard-level questions of Backtracking and understand its concept. These questions will help you to dive deep into it and if you follow this and previous blogs then I assure you that you will be able to implement at least 7 out of 10 questions of Recursion as well as backtracking on your own with your observation, and thinking in the right direction.
Table of Contents
1) Rat in a Maze Problem using Backtracking
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.
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.
#code
n = 4
def isSafe(maze, x, y):
if x >= 0 and x < n and y >= 0 and y < n and maze[x][y] == 1:
return True
return False
def SolveMazeUtil(maze, x, y, sol):
#If x and y is the goal then return True from here only
if x== n-1 and y==n-1 and maze[x][y] == 1:
sol[x][y] = 1
return True
#check if x-Y pos is valid
if isSafe(maze, x, y):
#if it is already part of sol
if sol[x][y] == 1:
return False
#mark x-y as safe
sol[x][y] = 1
#Move Forward in X-dir
if SolveMazeUtil(maze, x+1, y, sol):
return True
#If x does not give sol then try to move in Y dir
if SolveMazeUtil(maze, x, y+1, sol):
return True
#If moving forward in either X-Y does not give sol then Backtrack
if SolveMazeUtil(maze, x-1, y, sol):
return True
if SolveMazeUtil(maze, x, y-1, sol):
return True
sol[x][y] = 0
return False
def solveMaze(maze):
sol = [[0 for j in range(4)] for i in range(4)]
if SolveMazeUtil(maze, 0, 0, sol) == False:
print("Solution doesn't exist");
return False
#print(sol)
return True
maze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
print(solveMaze(maze))
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.
Input and Output Format
The first line of input contains the number of a test case and each line of the test case contains an integer 'N' denoting the size of the chessboard. For each test case, print all the possible solutions. If no solution is possible then print an empty list.
Example
Explanation
The 4 queens can be placed in a 4*4 chessboard in two ways. Both the configurations are shown below.
Backtracking Approach
Now think of the problem how we can approach this problem. So, in each row, we have to check each position that is it safe place to keep Queen and if it is safe then we can move to the next row and do the same till we do not reach the Nth row. And if in that row position is not safe then we have to move to the next column in the same row till we find a safe place in a row. Now if we are not able to find any safe place in that row it means that in the above row we have placed the queen in the wrong position so we will backtrack from there and change the position of a queen in the previous row. And in this way solution goes on.
After reading the above paragraph I hope that at least 60-70 percent of the approach is clear to it that how we can find the solution. The rest approach will be cleared to you when you observe the below dry-run approach to the problem.
How to check that position is safe or not?
This might be a question of some of you that how we will check that can we keep queen at a particular position. So all the conditions we already know that if one queen is already there in the same row, column, or diagonal then we cannot place a queen. So, we will have the position of row and column where we want to place a queen and we also know that the initial matrix contains all zeros it means if already queen is there then it can only be present before our current position. So we will check only in the above row and column position than the current position. Observe the below diagram for more clearance.
So, we have to only check in these three directions that if a queen is already present in this direction then we cannot place a queen at the current position. Else it is valid.
💻 Code ~ Now I think we can code the approach easily.
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.
Input-Output Format
We are given a 9*9 Matrix in which some numbers are filled and some are denoted with zero. Your task is to fill the zeros with a correct value that represents a valid sudoku solution.
Example
Backtracking Approach
After solving the N Queens problem I don't think that you cannot think of a solution to this problem because It is very similar in approach to the N queens problem. So the approach is we have to start from the top-left position array[0][0] to the bottom right array[8][8] and check for each position. If the position is already filled then we can simply move forward, Otherwise, it's our responsibility to find the digit between 1-9 which fits best at that position. This is a basic overview of the approach. Now let's see the step-by-step plan for how we can approach and solve this problem.
- First, we will implement a function that accepts a Grid, row, and column value. Initially, we have to start with a 0-0 position so the value of the row and column will be 0.
- Now we have to check If the current position is already filled then we have to move to the next position which has two cases.
- We have to see that the current column is not last, which means we have to move to the next row because the matrix end here.
- If we are not in the next column then in the same row we have to move forward means increasing the column by 1.
- If the value at the current position is empty(denoted as 0) then we will run a loop from 1 to 9 and for each value, we will check that if this position is safe for the value then we will insert that value. And then we will move forward in the same way as we have done in the above step.
- Now in any case, if we are not able to fill the next value in the next row, then we will backtrack to the previous value and make it zero, and check it for another value that is safe at that position.
In this way, if we successfully reach the last row and can fill it correctly then we have solved sudoku. So, our base case will be when row will be equal to 9 it means we have successfully reached to valid sudoku solution. And for checking the value is valid or not we will build a separate function to check the value should be unique in a row, column, and in a 3*3 sub-matrix.
💻 Code - Let's implement the approach using Python and it will more clear to you.
###CONSTRAINT-1 (All elements in row should be unique)
def row_valid(row, col, grid, k):
for i in range(9):
if grid[row][i] == k:
return False
return True
###CONSTRAINT-2 (All elements in column should be unique)
def column_valid(row, col, grid, k):
for i in range(9):
if grid[i][col] == k:
return False
return True
###CONSTRAINT-3 (All elements in sub-matrix should be unique)
## 9*9 grid divided into 3*3 sub-matrix of 9 elements
def subbox_valid(row, col, grid, k):
for i in range(0, 9, 3):
if row >= i and row < i+3:
row_start = i
row_end = i+3
if col >= i and col < i+3:
col_start = i
col_end = i+3
for i in range(row_start, row_end):
for j in range(col_start, col_end):
if grid[i][j] == k:
return False
#else k in unique so return True
return True
# Function which will check all the three cond is valid on element at cur pos
def valid(row, col, grid, k):
if (row_valid(row, col, grid, k) and column_valid(row, col, grid, k) and subbox_valid(row, col, grid, k)):
return True
return False
# Backtracking and solving SUDOKU Logic
def SUDOKU(i, j, grid):
## Base case
if i == len(grid):
return True
#If the element is present (already filled)
if grid[i][j] != 0:
if j == 8:
#chang the row(new row)
return SUDOKU(i+1, 0, grid)
else:
#chang the col
return SUDOKU(i, j+1, grid)
#Else element is not filled
for k in range(1, 10):
if valid(i, j, grid, k):
grid[i][j] = k
if j==8:
if(SUDOKU(i+1, 0, grid)):
return True
else:
if(SUDOKU(i, j+1, grid)):
return True
#Backtracking
grid[i][j] = 0
return False
def main(grid):
#If sol find then True, else False
print(SUDOKU(0, 0, grid))
global grid
grid = [ [3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]
]
main(grid)
#If you want to print the sol row-wise in space separated way
for row in grid:
print(*row)
🔖 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.
Thanks for your time! 😊