Scribd
Upload
11 views6 pages

Backtracking Algorithm Explained

Backtracking is a problem-solving algorithm that employs a brute force approach to explore all possible solutions and backtrack if a current solution is unsuitable. It utilizes recursion and is represented by a state space tree to visualize potential solutions. Examples include arranging individuals under constraints and solving the N-Queens problem, with time complexity of O(N * N!) and space complexity of O(N * N).

Uploaded by

92prajak sen
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views6 pages

Backtracking Algorithm Explained

Backtracking is a problem-solving algorithm that employs a brute force approach to explore all possible solutions and backtrack if a current solution is unsuitable. It utilizes recursion and is represented by a state space tree to visualize potential solutions. Examples include arranging individuals under constraints and solving the N-Queens problem, with time complexity of O(N * N!) and space complexity of O(N * N).

Uploaded by

92prajak sen
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Topic:- Backtracking

A backtracking algorithm is a problem-solving algorithm that uses a brute


force approach for finding the desired output.

The Brute force approach tries out all the possible solutions and chooses
the desired/best solutions.

The term backtracking suggests that if the current solution is not suitable,
then backtrack and try other solutions. Thus, recursion is used in this
approach.

State Space Tree


A space state tree is a tree representing all the possible states (solution or
nonsolution) of the problem from the root as an initial state to the leaf as a
terminal state.

Example Backtracking Approach


Problem: You want to find all the possible ways of arranging 2 boys and 1
girl on 3 benches. Constraint: Girl should not be on the middle bench.

Solution: There are a total of 3! = 6 possibilities. We will try all the


possibilities and get the possible solutions. We recursively try all the
possibilities.

All the possibilities are:


N QUEEN PROBLEMS

ALGORITHM
Time & Space Complexity
As we got to know in the algorithm for each cell, to check if the queen can be placed
there or not, we are iterating for N times. So the recurrence relation comes out to be:

T(N) = N * T(N-1) + N.

T(N-1) = N * T(N-2) + N

---------------------------

----------------------------

T(1) = 1

This totals T(N) = N* N!. therefore, the time complexity comes out to be O(N * N!).

And as we have used an extra board of characters of N x N Size, The space


complexity comes out to be O(N *N).
RAT IN MAZE

The rat in a maze problem is a path finding puzzle in which our


objective is to find an optimal path from a starting point to an
exit point. In this puzzle, there is a rat which is trapped inside a
maze represented by a square matrix. The maze contains
different cells through which that rat can travel in order to reach
the exit of maze.
Algorithms

You might also like