Project - Design And Analysis Algorithms
backtracking
Project by : Lakshya Sanghi
Branch : Computer Science & Engineering (Data Science)
Roll No. : 2021UCD2137
INTRODUCTION
Backtracking is an algorithmic technique for solving
problems recursively by trying to build a solution
incrementally, one piece at a time, removing those
solutions that fail to satisfy the constraints of the
problem at any point in time. Backtracking can also be
said as an improvement to the brute force approach.
So basically, the idea behind the backtracking
technique is that it searches for a solution to a
problem among all the available options.
PROBLEMS IN BACKTRACKING
There are 3 types of problems in backtracking :
1.Decision Problem : Here, we search for a feasible solution
2.Optimization Problem : Here, we search for the best solution
3.Enumeration Problem : Here, we find all feasible solutions
Working Of Algorithm
BACKTRACKING ALGORITHM
Backtrack(x)
if x is not a solution
return false
if x is a new solution
add to list of solutions
backtrack (expand x)
Applications Of
Backtracking Algorithm
1. N Queen Problem
This problem is to find an arrangement of N queens on a chess board. such that no queen
can attack any other queens on the board.
Input:
The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board)
Output:
The matrix that represents in which row and column the N Queens can be placed.
If the solution does not exist, it will return false.
10000000
00000010
00001000
00000001
01000000
00010000
00000100
00100000
In this output, the value 1 indicates the correct place for the queens.
The O denotes the blank spaces on the chess board.
Algorithm for N Queen Problem
solveNQueen (board, col)
Input-The chess board, the col where the queen is trying
to be placed.a
Output - The position matrix where queens are placed.
Begin
if all columns are filled, then
return true
for each row of the board, do
if isValid(board, I, col), then
set queen at place (i, col) in the board
if solveNQueen (board, col+1) = true, then
return true
otherwise remove queen from place (i, col) from board
done
return false
End
RAT IN MAZE PROBLEM
In this problem, there is a given maze of size N x N. The source and the destination
location is top-left cell and bottom right cell respectively. Some cells are valid to
move and some cells are blocked. If one rat starts moving from start vertex to
destination vertex, we have to find that is there any way to complete the path, if it
is possible then mark the correct path for the rat.
Input:
This algorithm will take the maze as a matrix.
In the matrix, the value 1 indicates the free space and 0 indicates the wall or
blocked area.
Output:
It will display a matrix. From that matrix, we can find the path of the rat to reach
the destination point.
ALGORITHM
solveRat(x, y)
Input-The starting point x and y.
Output - The path to follow by the rat to reach the destination, otherwise false.
Begin
if (x,y) is the bottom right corner, then mark the place a
return true
If isValidPlace(x, y) = true, then
mark (x, y) place as 1
if solveRatMaze (x+1, y) = true, then //for forward movement
return true
if solveRatMaze(x, y+1)= true, then //for down movement
return true
mark (x,y) as O when backtracks
return false
return false
End
