Unit 5
Backtracking
- by:
Dr. Varsha [Link]
Backtracking
• Backtracking is like trying different paths, and
when you hit a dead end, you backtrack to the
last choice and try a different route.
• Backtracking is a problem-solving algorithmic
technique that involves finding a solution
incrementally by trying different
options and undoing them if they lead to
a dead end.
• It is commonly used in situations where you
need to explore multiple possibilities to solve
a problem,
• like searching for a path in a maze or solving
puzzles like Sudoku.
• When a dead end is reached, the algorithm
backtracks to the previous decision point and
explores a different path until a solution is
found or all possibilities have been exhausted.
Types of Backtracking Problems
• Problems associated with backtracking can be categorized into 3
categories:
• Decision Problems
• These problems require determining whether a solution exist(yes/no)
• Example: Checking if a Hamiltonian cycle exists in a graph.
• 2. Optimization Problems
• These problems involve finding the best solution from multiple possible
solutions.
Example: The Traveling Salesman Problem (TSP)—finding the shortest
route covering all cities.
• 3. Constraint Satisfaction Problems (CSPs)
• Problems where a solution must satisfy a given set of constraints.
Example: Sudoku, n-Queens, Graph Coloring.
• Generally constraint satisfaction problem can be
solved using backtracking
• Backtracking problems involve two types of
constraints:
• 1. Explicit Constraints
• These define the properties of a valid solution.
• If an explicit constraint is violated, backtracking occurs
immediately.
• Examples-
• in n-Queens, no two queens should be in the same
row, column, or diagonal.
• In Graph Coloring, adjacent nodes must not have the
same color.
• Implicit Constraints
• These define the rules for selecting the next
possible solution step.
• They dynamically evolve as the solution is
built.
• Examples:
• In Sudoku, a number can be placed in a cell
only if it is not present in the same row,
column, or box.
• In Word Search, the next selected letter must
if it form a valid word.
Working of Backtracking Algorithm
• Choose a possible solution component.
• Verify if it satisfies constraints.
– If it satisfies, proceed to the next step.
– If it violates, backtrack and try another option.
• Repeat until a complete solution is found.
Backtracking Algorithm Structure
(Pseudocode)
Backtrack(solution):
if solution is complete:
process the solution
return
for each possible choice:
if choice is valid:
make the choice
Backtrack(solution) // Recursive call
undo the choice (backtrack) // Remove last step if needed
Detailed Explanation of the Steps
• Base Case:
– If the solution is complete, process it and return.
• Recursive Case:
– Loop through all possible choices at the current step.
– Check if a choice is valid (i.e., satisfies constraints).
– If valid, include the choice and move to the next step.
– If no valid solution is found, backtrack by undoing the
last choice.
How does Backtracking works?
graph coloring
problem with
examples
Graph coloring problem
• Graph coloring refers to the problem of
coloring vertices of a graph in such a way that
no two adjacent vertices have the same color.
• This is also called the vertex coloring problem.
• If coloring is done using at most m colors, it is
called m-coloring.
graph coloring problem
• Graph coloring problem is both, a decision
problem as well as an optimization problem.
• A decision problem is stated as, “With given
M colors and graph G, whether a such color
scheme is possible or not?”.
• The optimization problem is stated as, “Given
M colors and graph G, find the minimum
number of colors required for graph coloring.”
Applications of Graph Coloring
• Map Coloring -
– Ensures that no two adjacent regions (countries,
states, districts) share the same color.
– Used in geographical maps to differentiate
neighboring areas.
• Task Scheduling -
– Assigns resources (e.g., CPU, workers, classrooms) to
tasks while avoiding conflicts.
– Example: Parallel processing where dependent tasks
get different colors to avoid execution conflicts.
Applications of Graph Coloring
• Time Table Scheduling-
– Allocates different time slots for classes/exams
ensuring no two overlapping events occur at the
same time.
• Assignment Problems -
– Assigns workers to tasks, ensuring that no worker
is assigned two conflicting tasks.
– Example: Assigning interviewers to candidates in a
recruitment process.
Applications of Graph Coloring
• Conflict Resolution -
– Used in networks, databases, and traffic systems to
prevent conflicts.
– Example: Deadlock prevention in operating systems
by ensuring non-conflicting resource allocation.
• Sudoku Puzzle Solving -
– Each cell in a Sudoku grid represents a node in a
graph.
– Each number represents a different color.
Chromatic Number:
• The minimum number of colors needed to
color a graph is called its chromatic number.
• For example, the following can be colored a
minimum of 2 colors.