Backtracking at Five Levels

1. Child: Imagine you’re playing a game of maze. You’re trying to find a way out. So, you start walking and taking different turns. If you find a dead-end (a place where you can’t move forward), what do you do? You go back to the point where you took the last turn and then try a different path. That is backtracking.

2. Teenager: Think of backtracking like playing a video game. In some games, you have to explore different paths to find treasures or complete a mission. Sometimes, you’ll hit a dead-end, or find that a path is too dangerous. So, you go back to a safe point and try a different way. In computing, backtracking is a method where you try out different solutions until you find one that works.

3. Undergrad: In computer science, backtracking is an algorithmic-technique used for solving problems recursively by trying to build a solution incrementally, one piece at a time. If a solution we’re building turns out not to be satisfactory, we undo the last step (hence, ‘backtrack’) and try a different option.

4. Grad Student: Backtracking is a powerful algorithmic paradigm, often used to solve constraint satisfaction problems, like puzzles or optimization problems. Backtracking systematically explores all possible solutions of a problem by incrementally extending the current solution. If at any point it’s determined that the current solution can’t be extended into a complete one, the algorithm discards the current extension, and, in a depth-first manner, continues with the next available option.

5. Colleague: Backtracking operates by building tentative solutions one component at a time and abandoning a solution as soon as it determines that the current path cannot possibly be extended into a valid solution. It’s used in various practical scenarios like the Knapsack problem, the Eight Queens puzzle, or implementing regex parsers. The power of backtracking comes at the cost of potentially high time complexity due to the exploration of all paths, hence it’s our job to optimize it and reduce the search space, for instance through constraint propagation or variable/value ordering heuristics.

In simple term is it retracing the steps to go back to a previous step. Backtracking, in a general context, refers to the act of reverting or returning to a previous state, position, or condition after a situation has been evaluated or a decision has been made. It usually involves reversing or undoing steps, rethinking decisions, or reconsidering the direction of a particular strategy or approach. It is often used in the context of problem-solving, negotiation, or decision-making processes where a certain path did not lead to a desired outcome, so one must “track back” to an earlier point and try a different approach.

Socrates Teaches Backtracking

1. Have you ever found yourself in a maze, moving along a path, only to reach a dead-end? What would you typically do in such a situation?

2. Exactly! You would retrace your steps (or “go back”) until you find a spot where you can take a different path. This concept of retracing your steps and exploring alternative paths when you hit a dead-end is a common algorithmic technique. Can you think of any computer-related tasks where this approach would be beneficial?

3. Great examples! Problems like finding a way through a digital maze, arranging chess pieces in a certain way, or even finding the shortest path in a network can benefit from this kind of approach. If you were to write a program to perform this task, what tools or methods do you think you’d use?

4. Precisely! The idea of recursion, or having a function call itself until a certain condition is met, is commonly used to implement this kind of approach. The program would move along a path until it hits a dead-end, at which point it would “return” to a previous point and try a different path. Are there any obstacles or issues you think you might face when writing a program to do this?

5. Yes, exactly! This technique can be time-consuming and may not be the most efficient, as it can involve going down many dead-end paths before finding the correct one. We also need to be careful to avoid going in circles, or having the program keep trying the same failed path over and over.

Well done! You’ve got a good understanding of this “retrace and try a different path” technique, which many programmers refer to as backtracking! As with any algorithm, the key is to understand the problem you’re solving, the strengths and weaknesses of your approach, and to carefully implement it.

Richard Feynman Explanation

Alright, let’s think about this in terms of a labyrinth, or a maze. You’re standing at the entrance and your goal is to find your way to the center. You don’t have a map, so you have to figure it out by exploring.

So, you start walking. You take a turn here, another turn there, and so on. But let’s say you reach a dead end. What do you do? Well, you can’t go forward anymore, so you need to backtrack. You go back to the last turn you made and try a different path. If that leads to a dead end again, you backtrack once more.

This is what we mean by ‘backtracking’ in computer science. It’s a strategy used in algorithms to find the solution to a problem by incrementally building candidates for the solution and abandoning a candidate as soon as it is determined that the candidate cannot possibly be extended to a valid solution.

The classic puzzle that uses backtracking is the eight queens puzzle. In this puzzle, you’re trying to place eight queens on a chessboard such that no two queens threaten each other. You start placing queens one by one in different columns. If a queen placed in a column doesn’t give a valid arrangement, we backtrack and return false. If we have placed queens in all columns, it means we have found a solution.

The key concept here is that when we find that our current solution cannot be completed into a correct one, we stop further attempts and return to the previous stage of the problem, repeating this process until we either find a solution or all routes have been tried. Just like finding your way out of the labyrinth.

Robin Williams Explanation

Backtracking, my dear friends, is like the ultimate game of hide-and-seek. Imagine you’re in a maze, and you’re trying to find that piece of cheese at the end. But here’s the catch, there are countless dead ends!

So, what do you do? You start walking, you turn left, you turn right, you keep going until… BAM! You hit a wall. Now what? Do you bash your head against it? Nah, that’s gonna leave a mark. Do you sit down and cry? Tempting, but it’s not gonna get you that cheese.

No, my friend, what you do is backtrack. You turn around, you retrace your steps, and you try another path. Maybe this time you go right instead of left. Maybe this time you avoid that creepy corridor with the spider webs.

You keep doing this, going forward and stepping back, trying new paths and ditching the ones that don’t work, until finally, there it is: the glorious, delicious cheese! That’s backtracking!

In the realm of computer science, backtracking is essentially the same game. You’re trying to solve a problem, but there are lots of potential solutions. So, the computer tries one, and if it hits a dead end, it backtracks and tries another one. It’s like a game of ‘guess and check,’ but with a lot more guesswork, a lot less cheese, and thankfully, no spiders.

So, remember, whether you’re navigating a maze, solving a puzzle, or simply trying to choose a movie on a Friday night, don’t be afraid to backtrack! It’s not admitting defeat, it’s just part of the process. And who knows, you might just find your cheese at the end of the maze!

Example

A backtracking algorithm tries to construct a solution to a computational problem incrementally, one small piece at a time. Whenever the algorithm needs to decide between multiple alternatives to the next component of the solution, it recursively evaluates every alternative and then chooses the best one.

Imagine someone gave you a lock with a number (three digit lock, number range from 1 to 9). Moreover, you do not have the exact password key for the lock. You need to test every combination until you got the right one.

Obviously, you need to test starting from something like “111”, then “112” and so on. You will get your key before you reach “999”. This is backtracking.

Let’s say the lock produces a clicking sound when correct digit is selected for any level. If we can listen to this sound such intelligence / heuristics will help you to reach your goal much faster.

These functions are called Pruning function or bounding functions. Backtracking is a method by which solution is found by exhaustively searching through large but finite number of states, with some pruning or bounding function that will narrow down our search.

Backtracking problems have the following components:

1. Initial state
2. Target / Goal state
3. Intermediate states
4. Path from the initial state to the target / goal state
5. Operators to get from one state to another
6. Pruning function (optional)

The solving process of backtracking algorithm starts with the construction of state’s tree, whose nodes represents the states. The root node is the initial state and one or more leaf node will be our target state. Each edge of the tree represents some operation. The solution is obtained by searching the tree until a Target state is found.

Backtracking uses depth-first search:

1. Store the initial state in a stack
2. While the stack is not empty, repeat:
3. Read a node from the stack.
4. While there are available operators, do: a. Apply an operator to generate a child b. If the child is a goal state – return solution c. If it is a new state, and pruning function does not discard it push the child into the stack.

Recursion

Backtracking algorithms use recursion to search for the best solution to complicated problems. These algorithms recursively build partial test solutions to solve the problem. When they find that a test solution cannot lead to a usable final solution, they backtrack, discarding that test solution and continuing the search from an earlier test solution.

Partial Solutions

Backtracking is useful when you can incrementally build partial solutions, and you can sometimes quickly determine that a partial solution cannot lead to a complete solution. In that case, you can stop improving that partial solution, backtrack to the previous partial solution, and continue the search from there.

Partial Tasks

The common pattern is to decompose the trial-and-error process onto partial tasks. Often these tasks are most naturally expressed in recursive terms and consist of the exploration of a finite number of subtasks.

Pruning

We may generally view the entire process as a trial or search process that gradually builds up and scans a tree of subtasks. In many problems this search tree grows very rapidly, often exponentially, depending on a given parameter. The search effort increases accordingly. Frequently, the search tree can be pruned by the use of heuristics only, thereby reducing computation to tolerable bounds.

Exhaustive Search

In many real-world problems, as in most of the NP-hard problems, a solution can be obtained by exhaustively searching through a large but finite number of possibilities.

Moreover, for virtually all of these problems, there does not exist an algorithm that uses a method other than exhaustive search. Hence, the need arose for developing systematic techniques of searching, with the hope of cutting down the search space to possibly a much smaller space.

Backtracking is a general technique for organizing the search. This algorithm design technique can be described as an organized exhaustive search which often avoids searching all possibilities. It is generally suitable for solving problems where a potentially large but a finite number of solutions have to be inspected.

Brute Force and Backtracking

Backtracking is an improvement of the brute force approach. It systematically searches for a solution to a problem among all available options.

We start with on possible option out of many available options and try to solve the problem if we are able to solve the problem with the selected move. Then we will print the solution otherwise we will backtrack and select some other option and try to solve it. If none of the options work out, we will claim that there is no solution for the problem.

Applying Backtrack Method

In order to apply the backtrack method, the desired solution must be expressible as an n-tuple (x1 , …., xn) where the xi are chosen from some finite set Si. Often the problem to be solved calls for finding one vector which maximizes (or minimizes or satisfies) a criterion function P(x1, ….., xn).

The general principle consists of breaking up problem-solving tasks into subtasks and applying recursion.

Iterative Backtracking Program Template

Iterative Backtracking Method

Here’s a general backtracking algorithm which can be implemented iteratively:

1. Initialize a stack to store the states.
2. Push the initial state to the stack.
3. While the stack is not empty: a. Pop a state from the stack. b. If this state is the goal, return it as the solution. c. Generate all successors of this state. d. If a successor has not been visited yet and meets the conditions for pruning (if any), push it into the stack.

This algorithm uses Depth-First Search (DFS) to explore the state space of the problem. It systematically explores all possible solutions of the problem, but unlike Breadth-First Search (BFS), it goes deeper into a branch before exploring its neighbors.

The pruning step is optional and depends on the problem at hand. It’s a technique that allows the algorithm to avoid considering certain states or branches that are known to not contain a solution, reducing the amount of work that needs to be done.

In Python, this general iterative backtracking algorithm could look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def backtracking(start):
    stack = [start]
    while stack:
        state = stack.pop()
        if is_goal(state):
            return state
        for neighbor in get_neighbors(state):
            if should_prune(neighbor):
                continue
            stack.append(neighbor)
    return None  # No solution found

In this code:

• start is the initial state.
• is_goal(state) is a function that checks if a state is the goal state.
• get_neighbors(state) is a function that generates all successors of a state.
• should_prune(neighbor) is a function that checks if a state should be pruned.

These functions need to be defined according to the specifics of the problem that you are trying to solve. For example, in a maze solving problem, a state might represent the current position in the maze, get_neighbors(state) might return all adjacent cells that can be moved to, is_goal(state) might check if the current position is the exit of the maze, and should_prune(neighbor) might check if a cell has already been visited or if it’s a wall.

This is a general template and should be modified according to your specific use case. Please be aware that the above Python code doesn’t handle marking states as visited which is required for most problems to prevent infinite loops, so you should add that part to your own code as well.

Recursive Backtracking Program Template

The following pseudocode shows the general backtracking approach at a high level:

// Explore this test solution.
// Return false if it cannot be extended to a full solution.
// Return true if a recursive call to LeadsToSolution finds
// a full solution.
Boolean: LeadsToSolution(Solution: test_solution)
  // If we can already tell that this partial solution cannot
  // lead to a full solution, return false.
  If <test_solution cannot solve the problem> Then Return false
  // If this is a full solution, return true.
  If <test_solution is a full solution> Then Return true

  // Extend the partial solution.

  Loop <over all possible extensions to test_solution>      
    <Extend test_solution>
    // Recursively see if this leads to a solution.
    If (LeadsToSolution(test_solution)) Then Return true
    // This extension did not lead to a solution. Undo the change.
    <Undo the extension>
  End Loop
  // If we get here, this partial solution cannot
  // lead to a full solution.
  Return false
End LeadsToSolution

The LeadsToSolution algorithm takes as a parameter whatever data it needs to keep track of a partial solution. It returns true if that partial solution leads to a full solution.

The algorithm begins by testing the partial solution to see if it is illegal. If the test solution so far cannot lead to a feasible solution, the algorithm returns false. The calling instance of LeadsToSolution abandons this test solution and works on others.

If the test solution looks valid so far, the algorithm loops over all the possible ways that it can extend the solution toward a full solution. For each extension, the algorithm calls itself recursively to see whether the extended solution will work. If the recursive call returns false, that extension doesn’t work, so the algorithm undoes the extension and tries again with a new extension.

If the algorithm tries all possible extensions to the test solution and cannot find a feasible solution, it returns false so that the calling instance of LeadsToSolution can abandon this test solution.

You can think of the quest for a solution as a search through a hypothetical decision tree. Each branch in the tree corresponds to a particular decision attempting to solve the problem.

Backtracking allows us to deal with situations in which a raw brute-force approach would explode into an impossible number of options to consider.

At each node, we eliminate choices that are obviously not possible and proceed to recursively check only those that have potential. We back up only as far as needed to reach a previous decision point with an as-yet-unexplored alternative.

In general, that will be at the most recent decision point. Eventually, more and more of these decision points will have been fully explored and we will have to backtrack further and further.

If we backtrack all the way to our initial state and have explored all alternatives from there, we can conclude the particular problem is unsolvable. In such a case, we have done all the work of the exhaustive recursion and know that there is no viable solution possible.

The General Pattern

Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints. Often this goal structure is itself a sequence.

In each recursive call to the backtracking algorithm, we need to make exactly one decision, and our choice must be consistent with all previous decisions.

Thus, each recursive call requires not only the portion of the input data we have not yet processed, but also a suitable summary of the decisions we have already made. For the sake of efficiency, the summary of past decisions should be as small as possible.

When we design new recursive backtracking algorithms, we must figure out in advance what information we will need about past decisions in the middle of the algorithm. If this information is nontrivial, our recursive algorithm might need to solve a more general problem than the one we were originally asked to solve.

Finally, once we’ve figured out what recursive problem we really need to solve, we solve that problem by recursive brute force: Try all possibilities for the next decision that are consistent with past decisions, and let the recursion magic do the rest. No being clever here. No skipping “obviously” stupid choices. Try everything. You can make the algorithm faster later.

Conclusion

Backtracking is a technique where a recursive algorithm considers partial solutions. If it cannot extend a partial solution to a full solution, the algorithm discards the partial solution, backtracks to the previous feasible test solution, and continues searching from there. Examples include the eight queens problem and the knight’s tour problem.

References

• Fundamentals of Computer Algorithms by Horowitz and Sahni
• Essential Algorithms A Practical Approach to Computer Algorithms using Python and C by Rod Stephens

Why is backtracking called a modified depth-first search of a tree?

The backtracking algorithm traverses the search tree recursively, from the root down, in depth-first order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole sub-tree rooted at c is skipped (pruned). Otherwise, the algorithm:

1. Checks whether c itself is a valid solution, and if so reports it to the user; and
2. Recursively enumerates all sub-trees of c. The two tests and the children of each node are defined by user-given procedures.

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.

Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.

Pseudocode

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

1. root(P): return the partial candidate at the root of the search tree.
2. reject(P,c): return true only if the partial candidate c is not worth completing.
3. accept(P,c): return true if c is a solution of P, and false otherwise.
4. first(P,c): generate the first extension of candidate c.
5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
6. output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call bt(root(P)), where bt is the following recursive procedure:

1
2
3
4
5
6
7

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)

When to use backtracking to solve problems?

• You should use backtracking while solving crosswords, Sudoku and many other kind of puzzles.
• Backtracking method is mainly used for solving the constraint satisfactions problem where specific constrains are needed to be satisfied.
• It is also used for solving the problems related to the State space have size of factorial .Example of such problem is Travelling sales man Problem

In the real-world problems where you need to find the optimal solution out of many possible ones, the technique of backtracking becomes extremely handy. Here are a few examples of the types of problems where backtracking could be used:

1. Puzzle Games: Backtracking can be used in solving puzzles such as Sudoku and crosswords, where each step you take could potentially affect future steps. In the case of Sudoku, for instance, the player has to fill up the entire grid with numbers in such a way that no number is repeated in any row, column, or smaller grid. When the player fills in a number, they don’t know whether it’s correct until the end. If it turns out to be incorrect, they need to ‘backtrack’ and try a different number. This same process can be automated using backtracking algorithms.

2. Constraint Satisfaction Problems: In many decision-making tasks, you need to satisfy a set of constraints while optimizing some objective. These are known as constraint satisfaction problems. An example could be a scheduling task where you have to schedule jobs on machines such that the total time is minimized, and each job needs a specific machine for a specific amount of time. The problem becomes more complex when there are more jobs and machines. Backtracking helps you make decisions at each step, keeping in mind that if you cannot find an optimal solution down one path, you can go back and choose a different path.

3. Path Finding Problems: Backtracking can also be used in path-finding problems. In these problems, you need to find a path from a start point to an end point. A classic example of this is the maze-solving problem, where you need to find a way out of a maze. Backtracking allows you to go down a path and if you reach a dead-end or an already visited location, you backtrack and try another path.

4. NP-hard Problems: Backtracking can be used to solve NP-hard problems such as the traveling salesperson problem. This problem involves finding the shortest possible route that visits each city and returns to the origin city. A brute-force approach would involve calculating every possible route and then selecting the shortest, but this is not feasible for a large number of cities because of the factorial growth of possible routes. A backtracking approach, however, would construct a route piece by piece and abandon a route as soon as it is longer than the shortest route found so far.

In each of these examples, the approach is similar: make a choice and proceed with that choice until you either solve the problem or reach a point where you realize that the problem cannot be solved with the current set of choices. If you reach such a point, you undo the last choice (i.e., you ‘backtrack’) and make a different choice. Repeat this process until you find a solution or exhaust all your choices. The power of backtracking lies in the fact that it prunes the search space, thus allowing solutions to be found more efficiently.

Language Agnostic Coding Drills

Backtracking is a general algorithmic technique that involves exploring every possible option in order to solve a problem. Here are the key concepts involved in understanding and implementing backtracking algorithms:

1. Problem Understanding: Understand what backtracking is and when it is used.

   • Drill: Write a simple problem statement that can be solved using backtracking, such as the N-Queens problem or the Sudoku solver problem.

2. Basic Control Structures: Understand conditional (if-else) statements and loops.

   • Drill: Write a simple program that reads a series of numbers and prints the largest one.

3. Understanding Recursion: Backtracking involves recursion, as the solution to the problem involves exploring every possible option and backtracking when a particular path does not provide a solution.

   • Drill: Write a recursive function that calculates the factorial of a number.

4. Backtracking Basics: Understand the basic structure of a backtracking algorithm, which involves a recursive function that tries every possible option and backtracks when a path does not lead to a solution.

   • Drill: Write a simple backtracking algorithm that solves a simple problem, such as generating all the permutations of a string.

5. Problem-Specific Considerations: Every backtracking problem will have certain problem-specific considerations, such as how to quickly check if a solution is valid in the N-Queens problem, or how to efficiently generate potential next moves in the Sudoku solver problem.

   • Drill: Write a function that solves a problem-specific aspect of a backtracking problem, such as checking if a queen can be placed in a certain position in the N-Queens problem.

6. Implementing the Full Solution: After understanding the basics of backtracking and the problem-specific considerations, the final step is to implement the full solution to the backtracking problem.

   • Drill: Implement the full solution to a backtracking problem, such as the N-Queens problem or the Sudoku solver problem.

The above drills start from understanding the problem and the basics of control structures and recursion, gradually build up understanding of the backtracking technique, and finally involve implementing a full solution to a backtracking problem.

Solution for Coding Drills in Python

Here are Python code snippets that illustrate each of the drills for the N-Queens problem using backtracking:

1. Problem Understanding

   • The N-Queens problem is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

2. Basic Control Structures

   • Print the largest number from a series of numbers:

1
2
3
4
5
6
7
8

numbers = [4, 2, 9, 7, 5, 1]
max_number = numbers[0]

for num in numbers:
    if num > max_number:
        max_number = num

print(max_number)

3. Understanding Recursion
   • Calculate the factorial of a number:

1
2
3
4
5
6
7

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # Output: 120

4. Backtracking Basics
   • Generate all the permutations of a string:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def permute(data, i, length): 
    if i == length: 
        print(''.join(data))
    else: 
        for j in range(i, length): 
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]

string = "ABC"
permute(list(string), 0, len(string))

5. Problem-Specific Considerations
   • Check if a queen can be placed in a certain position in the N-Queens problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def is_safe(board, row, col, N):
    # Check the row on left side
    for i in range(col):
        if board[row][i] == 1:
            return False

    # Check upper diagonal on left side
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Check lower diagonal on left side
    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True

6. Implementing the Full Solution
   • Here’s the solution to the N-Queens problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def solve_n_queens(board, col, N):
    if col >= N:
        return True
    for i in range(N):
        if is_safe(board, i, col, N):
            board[i][col] = 1
            if solve_n_queens(board, col + 1, N):
                return True
            board[i][col] = 0
    return False

def solve(N):
    board = [[0]*N for _ in range(N)]
    if not solve_n_queens(board, 0, N):
        print("Solution does not exist.")
        return False
    print(board)
    return True

solve(4)