************
Backtracking
************

Definition
==========
Backtracking is a general algorithmic technique that involves exploring all
possible solutions to a problem by building solution candidates incrementally
and abandoning a candidate ("backtracking") as soon as it is determined that
the candidate cannot be extended to a valid solution. It's essentially a trial
and error approach, where potential solutions are built piece by piece and
abandoned when they fail to meet the necessary criteria.

Backtracking is a fundamental concept in computer science, especially in the
domain of algorithms and problem-solving. It's particularly useful for solving
constraint satisfaction problems, optimization problems, and combinatorial
problems. Some classic examples include the N-Queens puzzle, the traveling
salesman problem, and various game-solving algorithms like Sudoku. Its
importance lies in its ability to find solutions to problems where the solution
space is vast and cannot be traversed in a straightforward manner. By
systematically trying out different solutions and backtracking when necessary,
efficient solutions can be found for many complex problems.

Core Concepts
=============
+ Backtracking operation:

  The backtracking operation is the core of the backtracking algorithm. The
  backtrack operation is used to undo a decision and try another decision at a
  decision point.

+ Decision Space:

  The decision space refers to all the possible options or choices available at
  any given point in the problem-solving process. In backtracking, not all
  decisions in this space lead to a valid solution. The algorithm explores
  these decisions systematically, often visualized as a tree or graph, where
  each node represents a decision.

+ Feasibility Checks:

  Before or after making a decision, it's essential to check if the current
  path being taken is feasible. This involves ensuring that the current
  solution candidate adheres to the problem's constraints. If a decision fails
  the feasibility check, the algorithm will backtrack to a previous decision
  point.

+ Solution Space:

  The solution space encompasses all potential solutions to the problem. It's
  the set of all paths or decision sequences that lead to a valid solution.
  Backtracking navigates this space by exploring and discarding paths, aiming
  to find one or more paths that lead to a valid solution.


Implementation
==============
Implementation may vary depending on the problem, but the general approach is
either recursive or iterative. The recursive approach is more intuitive. The
iterative approach requires the use of a stack data structure to keep track of
the current state and the current path being explored.

+ Recursive approach

.. code-block::

  function BACKTRACKING-SOLUTION(problem):
      if problem is a base case:
          return solution to the base case
      for each option in problem:
          if option is valid:
              make the option
              result = BACKTRACKING-SOLUTION(sub-problem created by the option)
              if result is a valid solution:
                  return result
              undo the option (backtrack)
      return no solution found

+ Iterative approach

  * Stack data structure

.. code-block::

  function ITERATIVE-BACKTRACKING-SOLUTION(initialProblem):
      create an empty stack S
      push initialProblem onto S

      while S is not empty:
          currentProblem = top of S

          if currentProblem is a solution:
              return currentProblem

          if currentProblem has unexplored options:
              nextOption = get next unexplored option for currentProblem

              if nextOption is valid:
                  push nextOption onto S
              else:
                  mark nextOption as explored for currentProblem

          else:
              // All options for currentProblem have been explored, backtrack
              pop S

      return no solution found


+ Variations according to the goal

  * find one solution
  * find all solutions

Application Domain
==================
Backtracking algorithms are often used for optimization problems and
combinatorial problems, where you need to search through a large solution
space. They can be very efficient when implemented correctly, as they prune the
search space by discarding branches that are guaranteed not to lead to a
solution.

+ Enumeration (find all)
+ Decision (find one)
+ Optimization (find the best)

  * Find all and then select the best
  * Not as efficient as branch and bound

.. backtracking-example:

Example problems
----------------
+ Sudoku
+ Eight queens
+ Cross-word

Related Algorithms and Paradigms
================================
+ Brute-Force

  Brute-force is a general algorithmic paradigm that involves exploring all
  possible solutions to a problem by generating all possible candidates and
  validating them. It's similar to backtracking in that it involves exploring a
  decision space, but it's less efficient as it doesn't prune the search space
  and it doesn't use backtracking to discard invalid candidates. Brute-force
  algorithms can cover a wide spectrum of problems as all possible solutions
  are explored. It can be used to find all solutions, any valid solution, or
  the best solution. Backtracking is a more specific algorithmic paradigm that
  focus on to find any valid solution to a constraint satisfaction problem.
  When backtracking is employed to find all solutions, it is still more
  efficient than brute-force as it prunes the search space by discarding
  invalid candidates as early as possible.

+ Depth-First Search

  Both backtracking and depth-first search involve exploring a decision space
  or tree/graph space in a systematic manner. They both try to explore as deep
  as possible. The difference is that backtracking is used to find solutions to
  constraint satisfaction problems, while depth-first search is used to find
  paths/nodes in a graph or tree. Backtracking is a general algorithmic
  paradigm, while depth-first search is a specific algorithm that uses
  backtracking, which backtracks when it reaches a dead end.

+ Branch and bound

  Branch and bound is a general algorithmic paradigm that involves exploring
  the solution space by branching out and bounding the search space. It's
  similar to backtracking in that it involves exploring a decision space, but
  it's more efficient as it prunes the search space by bounding the solution
  space. The purposes of branch and bound are to find the optimal solution
  while backtracking is to find any valid solution. Branch and bound is often
  used for optimization problems, while backtracking is used for constraint
  satisfaction problems.

.. backtracking-exhaustive-comp:

Comparison
==========
.. list-table:: Backtracking vs Brute-force
  :header-rows: 1
  :stub-columns: 1
  :widths: 20 30 30

  * -
    - Backtracking
    - Brute-force
  * - Search space
    - Generate part of the intermediate and final states
    - Generate all intermediate and final states
  * - Constraint application
    - Reject partial solutions
    - Validate final states
  * - Run-time
    - fast
    - slow
  * - Implementation
    - Stack/Recursion
    - Nested Loops/Recursion
  * - Problem type
    - find one/find all
    - usually find all