Backtracking

@backtracking

Backtracking is a problem-solving technique used in algorithms to find a solution by exploring all possible solutions and retracting when a dead end is reached. It's often used for solving puzzles, finding paths, or scheduling tasks.

Pseudo-code
function backtrack(candidate):
  if candidate is a solution:
    return candidate
  for each neighbor of candidate:
    if neighbor is not visited:
      mark neighbor as visited
      result = backtrack(neighbor)
      if result is not false:
        return result
    unmark neighbor as visited
  return false
function solve():
  candidate = initial state
  while candidate is not false:
    candidate = backtrack(candidate)
  • path A list of steps or decisions made during the search.
  • candidate A potential solution being explored.
  • solution The final solution found or the best solution so far.
  • false A boolean value indicating the end of a dead end.
Recipe Steps
1

Think of a problem like finding a treasure in a maze. You have a map to help you find the treasure.

2

Start from the beginning of the maze and try to reach the treasure. If you get stuck, go back to a previous place and try a different path.

3

Keep trying different paths until you find the treasure or run out of paths to try.

4

If you run out of paths to try, you might need to go back to the beginning and start again.

Questions & Answers

Backtracking is a way to solve problems by trying different paths and going back if you get stuck.

We use backtracking to solve problems that have multiple possible solutions and we need to find one that works.

A dead end is a point in the search where we have tried all possible paths and we need to go back and try something else.
- Special tip: Backtracking can be slow if the problem has many possible paths.
- Gotcha: Make sure to keep track of the paths you have tried to avoid getting stuck in an infinite loop.

Related Algorithms
HeapSort

HeapSort is a sorting algorithm that uses a special tree structure called a heap. It repeatedly takes the largest element and moves it to the end, shrinking the unsorted part step by step until everything is sorted.

View