Scribd
Upload
116 views10 pages

Backtracking Techniques in IT

The document discusses backtracking as a technique to solve problems with large search spaces. It provides examples of how backtracking can be used to solve the 4-Queens problem and graph coloring problem. The key aspects of backtracking covered are building solutions incrementally and removing solutions that violate constraints, representing the state space as a tree, and classifying nodes in the tree as live, e-nodes, or dead nodes to track progress through the search space.

Uploaded by

Manohar Datt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
116 views10 pages

Backtracking Techniques in IT

The document discusses backtracking as a technique to solve problems with large search spaces. It provides examples of how backtracking can be used to solve the 4-Queens problem and graph coloring problem. The key aspects of backtracking covered are building solutions incrementally and removing solutions that violate constraints, representing the state space as a tree, and classifying nodes in the tree as live, e-nodes, or dead nodes to track progress through the search space.

Uploaded by

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

Lecture

ON

Backtracking

V.Radhesyam
Assistant professor
Department of IT:VRSEC
What is Backtracking
• Backtracking is a design technique used to
solve problems with large search space.

• Build a solution incrementally, one piece at


a time, removing those solutions that fail to
satisfy the constraints of the problem at
any point of time.

• Backtracking uses a data structure called


state space tree.
What is 4-Queens Problem
• The 4-Queens Problem consists in placing
four queens on a 4 x 4 chessboard so that
no two queens can attack each other.
• That is, no two queens are allowed to be
placed on the same row, the same column
or the same diagonal.
• This problem can be solved by backtracking
Complete State space Tree

4
Solution: State space Tree

x1=1 means Q1 Placed in first column


Chess board example
Types of nodes
• Live node: A node which is generated and
the children are not yet generated is called
live node.

• E-node: The node whose children are


currently generated is called E-node.

• Dead node: A node which cannot further


extended is called dead node.
Control abstraction
Graph coloring
• The problem is, given m colors, find a way of
coloring the vertices of a graph such that no two
adjacent vertices are colored using same color.
• This number is called chromatic number
Hamilton cycles
• Hamiltonian Path in an undirected graph is a path that
visits each vertex exactly once. A Hamiltonian cycle is a
Hamiltonian Path such that there is an edge (in graph) from
the last vertex to the first vertex of the Hamiltonian Path

You might also like