Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

UNIT - V : BACKTRACKING

General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring – Hamiltonian Cycles

General Method


Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step:

  1. Start with a choice: Make a decision and move forward.
  2. Check feasibility: If this choice leads to a solution or partial solution, continue. If not, stop exploring this path.
  3. Go back and try a different path: If you reach a dead end, go back to the last point where you made a choice. Try a different path from there.
  4. Repeat until you find a solution or exhaust all possibilities.

Backtracking is commonly used in puzzles and problems where you need to explore multiple paths, like mazes, Sudoku, and the N-Queens problem. 


N-Queens Problem

The N-Queens Problem is a classic puzzle where the goal is to place N queens on an N×N  chessboard so that no two queens can attack each other.

In simple terms:

  1. Goal: Place N queens on the board, with one queen in each row and each column.
  2. Rules: Queens should not be able to attack each other, which means no two queens can be in the same row, column, or diagonal.
  3. Backtracking: Place queens one by one, checking each time if it’s safe. If you can’t place a queen without conflict, "backtrack" by removing the last placed queen and trying a new position.

The time complexity of the N-Queens problem using backtracking is O(N!).

The N-Queens Problem demonstrates backtracking because you keep trying different placements and undo choices when conflicts arise.


Sum of Subsets

The Sum of Subsets problem in backtracking involves finding subsets of a given set of numbers that add up to a specific target sum.

  1. Goal: Find combinations of numbers in a set that add up exactly to a target sum.
  2. Process: Start with an empty subset, add numbers one by one, and keep checking the sum.
  3. Backtrack if needed: If the sum becomes too large, "backtrack" by removing the last number and trying the next one.
  4. Repeat until you’ve checked all possible combinations of numbers in the set.

Backtracking is helpful here because it lets us stop exploring combinations early if they exceed the target sum, making the process faster.  

The time complexity of the Sum of Subset problem using backtracking is O(2^n) in the worst case.

Example:

Consider the sum-of-subset problem, n = 4, Set S={3,5,6,7} and Sum = 15. Show the state-space tree leading to the solution. Also, number the nodes in the tree in the order of recursion calls.


Graph Colouring

Graph colouring is a way of assigning colours to the nodes (or vertices) of a graph so that no two connected nodes have the same color.

  1. Goal: Color each node in a graph with the minimum number of colours so that no two connected nodes share the same color.
  2. Rules: If two nodes are connected by an edge, they must be different colours.
  3. Backtracking (optional): In some cases, backtracking is used to try colours and go back if they lead to a conflict, ensuring a correct colouring.

Graph colouring is often used in scheduling problems, like assigning time slots to exams so no two exams with overlapping students are scheduled at the same time.

The time complexity of the graph colouring problem using backtracking is O(m^V), where

  • m: Number of colors available
  • V: Number of vertices in the graph


Hamiltonian Cycle

A Hamiltonian Cycle is a path in a graph that visits every node (or vertex) exactly once and then returns to the starting node, forming a cycle.

In simple terms:

  1. Goal: Find a cycle that visits every node once and returns to the starting point.
  2. Backtracking: Start at a node and try to visit each neighbouring node one by one, marking nodes as visited.
  3. Undo if necessary: If a path doesn’t lead to a cycle, "backtrack" by unmarking the last node and trying a different neighbour.
  4. Repeat until you either find a Hamiltonian Cycle or exhaust all possible paths.

Backtracking is useful here because it allows you to explore all possible routes efficiently, discarding paths that can’t complete the cycle early.

The time complexity of the Hamiltonian Cycle problem using backtracking is O(N!) in the worst case, where N is the number of vertices in the graph.



 

 

 

 

Comments

Post a Comment

Popular posts from this blog

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more