Backtracking – What, Why, and How?

What is Backtracking?

Backtracking is an intelligent way of gradually building the solution. Typically, it is applied to constraint satisfaction problems like Sudoku, crossword, 8-queen puzzles, chess, and many other games. Dynamic programming and greedy algorithms are optimization techniques, whereas backtracing is s general problem-solving method. It does not guarantee an optimal solution.

• A solution to many problems can be viewed as the making of a sequence of decisions. For example, TSP can be solved by making the sequence of the decision of which city should be visited next.
• Similarly, a knapsack is also viewed as a sequence of decisions. At each step, the decision to select or reject the given item is made.
• Backtracking builds the solution incrementally. Partial solutions that do not satisfy the constraints are abandoned.
• Backtracking is a recursive approach, and it is a refinement of the brute force method. The brute force approach evaluates all possible candidates, whereas backtracking limits the search by eliminating the candidates that do not satisfy certain constraints. Hence, backtracking algorithms are often faster than brute force approaches.
• Backtracking algorithms are used when we have a set of choices, and we don’t know which choice will lead to the correct solution. The algorithm generates all partial candidates that may generate a complete solution.
• The solution in backtracking is expressed as an n-tuple (x1, x2,… xn), where xi is chosen from the finite set of choices, Si. Elements in the solution tuple are chosen such that they maximize or minimize the given criterion function C(x1, x2,…, xn).
• Let C be the set of constraints on problem P, and let D is the set of all the solutions that satisfy the constraints C. Then
  • Finding if a given solution is feasible or not is the decision problem.
  • Finding the best solution is the optimization problem.
  • Listing all feasible solutions is an enumeration problem.
• Backtracking systematically searches the set of all feasible solutions, called solution space, to solve the given problem.
• Each choice leads to a new set of partial solutions. Partial solutions are explored in DFS (Depth First Search) order.
• If a partial solution satisfies a certain bounding function, then the partial solution is explored in depth-first order.
• If the partial solution does not satisfy the constraint, it will not be explored further. The algorithm backtracks from that point and explores the next possible candidate.
• Such processing is convenient to represent using a state space tree. In a state space tree, the root represents the initial state before the search begins.
• Figure (a) shows the workings of backtracking algorithms. It keeps exploring the partial solution by adding the next possible choice in the DFS order and building the new partial solution. This process continues till a partial solution satisfies the given constraints or a solution is not found. This is an incremental approach.

A node in the state-space tree is called promising if it represents a partially constructed solution which may lead to a complete solution. Non-promising node violates constraints and hence cut down from further computation.

A leaf node is either a non-promising node or represents a complete solution.

We can consider the backtracking process as finding a particular leaf in the tree. It works as follows :

• If node N is the goal node, then return success and exit.
  • If nodis a is leaf node not a ode goal nothen it hen returns failure.
• Otherwise, for each child C of node N,
  • Explore child node C
  • If C is the goal node, return “success”
  • Return failure
• In backtracking, the solution is expressed in form of tuple (x1, x2, …, xn), each xi ∈ Si, where Si is some finite set of choiceThe backtracking g algorithm tries to maximize or minimize certain criterion function f(.) by selecting or not selecting item xi.
• While solving the problem, the backtracking method imposes two constraints:
  • Explicit constraints : it restricts the section of xi from Si. Explicit constraints are problem-dependent. Allfrom the es from solution space must satisfy explicit constraints.
  • Implicit constraints : Such constraints determine which tuple in solution space satisfies the criterion function.

Examples:

• Sum of subset problem : Given the set of positive integers, problem is finding the combination of numbers that sum to given value N.

         i.e. if we are given a set of n positive numbers W = (w₁, w₂, w₃, …, w_n), then find the subset of integers from W such that it sum to N.

• Explicit constraint : Any integer w_i which is part of solution must belong to W.
• Implicit constraint 
  • Element must not be repeated
  • Sum of elements in selected sub set must be N
  • Order or elements in subset is immaterial i.e (w₁, w₄, w₇) = (w₄, w₇, w₁)
• Four queen problem : Given 4 ´ 4 chess board, arrange four queens in a way, such that no two queens attack each other. That is, no two queens are placed in same row, column or diagonal.
• Explicit constraint : On 4 ´ 4 chess board, only four rows and columns are possible. Hence solution space must be Si = {1, 2, 3, 4}.
• Implicit constraint  
  • No two queens can be in same rows.
  • No two queens can be in same columns.
  • No two queens can be in same diagonal.
  • No two x_i can be same.

Terminology

• The state space of the system is the set of states in which the system can exist.
• Solution to the problem which is derived by making sequence of decisions can be represented using state space tree T.
• The root of the tree is the state before making any decision. Nodes at the first level in the tree corresponding to all possible choices for the first decision.
• Nodes at second level corresponding to all possible choices for the second decision and so forth.
• Usually, number of decision sequence is in exponential order of input size n.
• State space for the 8-puzzle problem is shown in the Figure (b).

• Backtracking guaranteed to find the solution to any problem modeled by a state space tree.
• Based on traversal order of the tree, two strategies are defined to solve the problem.
• Backtracking traverse the tree in depth-first order
• Branch and bound traverse the tree in breadth-first order
• As backtracking always explores the current node first, there is no need of explicitly implementing the state space tree.
• Some terminologies related to state space tree are discussed here:

(1)    Solution space : The collection of all feasible solutions is called solution space.

(2)    State space : All the paths in the tree from root to other nodes form the state space of the given problem.

(3)    Problem state : Each node in the state space tree represents the problem state.

(4)    Answer state : Answer state is the leaf in the state space tree which satisfies the implicit constraints.

(5)    Solution-state : State S for which the path from the root to S represents a tuple in the solution space is called solution state.

(6)    Live node : In state space tree, a node that is generated but its children are yet to be generated is called a live node.

(7)    E-Node : Live node whose children are currently being explored is called E (Expansion) node.

(8)    Dead node : In state space tree, a node that is generated and either it’s all children are generated or node will not be expanded further due to a violation of criterion function, is called a dead node.

(9)    Bounding Functions : The bounding function kills the live node without exploring its children if the bound value of the live node crosses the bound limits.

(10) Static tree : If a tree is independent of an instance of the problem being solved, it is called a static tree

(11) Dynamic tree : If the tree depends on an instance of the problem being solved, it is called a dynamic tree.

Applications of Backtracking

Backtracking is useful in solving the following problems:

• N-Queen problem
• Sum of subset problem
• Graph coloring problem
• Knapsack problem
• Hamiltonian cycle problem
• Games like chess, tic-tac-toe, Sudoku etc.
• Constraint satisfaction problems
• Artificial intelligence
• Network communication
• Robotics
• Optimization problems
• It is also a basis of a logic programming language called PROLOG.

---

Additional Reading: Read More