Last modified: September 23, 2024
This article is written in: πΊπΈ
Backtracking is a systematic method for solving problems that incrementally build candidates to the solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. This approach is often used for constraint satisfaction problems, combinatorial optimization, and puzzles like the NQueens problem or Sudoku.
Recursive Functions
Recursive functions are functions that call themselves directly or indirectly to solve a problem by breaking it down into smaller, more manageable subproblems. This concept is fundamental in computer science and mathematics, as it allows for elegant solutions to complex problems through repeated application of a simple process.
Main idea:
 Base Case (Termination Condition) is the condition under which the recursion stops. It prevents infinite recursion by providing an explicit solution for the simplest instance of the problem.
 Recursive Case is the part of the function where it calls itself with a modified parameter, moving towards the base case.
Mathematical Foundation
Recursion closely relates to mathematical induction, where a problem is solved by assuming that the solution to a smaller instance of the problem is known and building upon it.
A recursive function can often be expressed using a recurrence relation:
$$ f(n) = \begin{cases} g(n) & \text{if } n = \text{base case} \\ h(f(n  1), n) & \text{otherwise} \end{cases} $$
where:
 $g(n)$ is the base case value,
 $h$ is a function that defines how to build the solution from the smaller instance.
Example: Calculating Factorial
The factorial of a nonnegative integer $n$ is the product of all positive integers less than or equal to $n$. Mathematically, it is defined as:
$$ n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n  1)! & \text{if } n > 0 \end{cases} $$
Python Implementation:
def factorial(n):
if n == 0:
return 1 # Base case: 0! = 1
else:
return n * factorial(n  1) # Recursive case
Detailed Computation for $n = 5$
Let's trace the recursive calls for factorial(5)
:
 Call:
factorial(5)
 Since $5 \neq 0$, compute $5 \times factorial(4)$.
 Call:
factorial(4)
 Compute $4 \times factorial(3)$.
 Call:
factorial(3)
 Compute $3 \times factorial(2)$.
 Call:
factorial(2)
 Compute $2 \times factorial(1)$.
 Call:
factorial(1)
 Compute $1 \times factorial(0)$.
 Call:
factorial(0)
 Base case reached: return $1$.
Now, we backtrack and compute the results:
factorial(1)
returns $1 \times 1 = 1$.factorial(2)
returns $2 \times 1 = 2$.factorial(3)
returns $3 \times 2 = 6$.factorial(4)
returns $4 \times 6 = 24$.factorial(5)
returns $5 \times 24 = 120$.
Thus, $5! = 120$.
Visualization with Recursion Tree
Each recursive call can be visualized as a node in a tree:
factorial(5)

+ factorial(4)

+ factorial(3)

+ factorial(2)

+ factorial(1)

+ factorial(0)
The leaves represent the base case, and the tree unwinds as each recursive call returns.
Important Considerations:
 When using recursion, ensure termination by designing the recursive function such that all possible paths eventually reach a base case. This prevents infinite recursion.
 Be mindful of stack depth, as each recursive call adds a new frame to the call stack. Too many recursive calls, especially in deep recursion, can result in a stack overflow error.
 Consider efficiency when choosing a recursive approach. While recursive solutions can be elegant and clean, they may not always be optimal in terms of time and space, particularly when dealing with large input sizes or deep recursive calls.
DepthFirst Search (DFS)
DepthFirst Search is an algorithm for traversing or searching tree or graph data structures. It starts at a selected node and explores as far as possible along each branch before backtracking.
Main idea:
 The traversal strategy of DepthFirst Search (DFS) involves exploring each branch of a graph or tree to its deepest point before backtracking to explore other branches.
 Implementation of DFS can be achieved either through recursion, which implicitly uses the call stack, or by using an explicit stack data structure to manage the nodes.
 Applications of DFS include tasks such as topological sorting, identifying connected components in a graph, solving puzzles like mazes, and finding paths in trees or graphs.
Algorithm Steps
 Start at the root node by marking it as visited to prevent revisiting it during the traversal.
 Explore each branch by recursively performing DFS on each unvisited neighbor, diving deeper into the graph or tree structure.
 Backtrack once all neighbors of a node are visited, returning to the previous node to continue exploring other branches.
Pseudocode:
DFS(node):
mark node as visited
for each neighbor in node.neighbors:
if neighbor is not visited:
DFS(neighbor)
Example: Tree Traversal
Consider the following tree:
A
/ \
B C
/ \
D E
Traversal using DFS starting from node 'A':
 Visit 'A' to begin the traversal, marking it as visited.
 Move to 'B', but since 'B' has no unvisited neighbors, backtrack to 'A' to explore other branches.
 Move to 'C', continuing the traversal to the next unvisited node.
 Move to 'D', but as 'D' has no unvisited neighbors, backtrack to 'C'.
 Move to 'E', but since 'E' also has no unvisited neighbors, backtrack to 'C', and then further backtrack to 'A' to complete the exploration.
Traversal order: A β B β C β D β E
Implementation in Python:
class Node:
def __init__(self, value):
self.value = value
self.children = []
self.visited = False
def dfs(node):
node.visited = True
print(node.value)
for child in node.children:
if not child.visited:
dfs(child)
# Create nodes
node_a = Node('A')
node_b = Node('B')
node_c = Node('C')
node_d = Node('D')
node_e = Node('E')
# Build the tree
node_a.children = [node_b, node_c]
node_c.children = [node_d, node_e]
# Perform DFS
dfs(node_a)
Analysis:
 The time complexity of DepthFirst Search (DFS) is $O(V + E)$, where $V$ represents the number of vertices and $E$ represents the number of edges in the graph.
 The space complexity is $O(V)$, primarily due to the space used by the recursion stack or an explicit stack, as well as the memory required for tracking visited nodes.
Applications
 Cycle detection in directed and undirected graphs.
 Topological sorting in directed acyclic graphs (DAGs).
 Solving mazes and puzzles by exploring all possible paths.
 Identifying connected components in a network or graph.
Backtracking
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, removing solutions that fail to satisfy the constraints at any point.
Main Idea:
 Building solutions one piece at a time and evaluating them against the constraints.
 Early detection of invalid solutions to prune the search space.
 When a partial solution cannot be extended to a complete solution, the algorithm backtracks to try different options.
General Algorithm Framework
 Understand the possible configurations of the solution.
 Start with an empty solution.
 At each step, try to add a new component to the solution.
 After adding a component, check if the partial solution is valid.
 If not valid, backtrack.
 If the partial solution is complete and valid, record or output it.
 If all options are exhausted at a level, remove the last component and backtrack to the previous level.
NQueens Problem
The NQueens problem is a classic puzzle in which the goal is to place $N$ queens on an $N \times N$ chessboard such that no two queens threaten each other. In chess, a queen can move any number of squares along a row, column, or diagonal. Therefore, no two queens can share the same row, column, or diagonal.
Objective:
 Place $N$ queens on the board.
 Ensure that no two queens attack each other.
 Find all possible arrangements that satisfy the above conditions.
Visual Representation
To better understand the problem, let's visualize it using ASCII graphics.
Empty $4 \times 4$ Chessboard:
0 1 2 3 (Columns)
+++++
0    
+++++
1    
+++++
2    
+++++
3    
+++++
(Rows)
Each cell can be identified by its row and column indices ((row, column)).
Example Solution for $N = 4$:
One of the possible solutions for placing 4 queens on a $4 \times 4$ chessboard is:
0 1 2 3 (Columns)
+++++
0 Q     (Queen at position (0, 0))
+++++
1   Q   (Queen at position (1, 2))
+++++
2    Q  (Queen at position (2, 3))
+++++
3  Q    (Queen at position (3, 1))
+++++
(Rows)
Q
represents a queen. Blank spaces represent empty cells.
Constraints
 Only one queen per row.
 Only one queen per column.
 No two queens share the same diagonal.
Approach Using Backtracking
Backtracking is an ideal algorithmic approach for solving the NQueens problem due to its constraint satisfaction nature. The algorithm incrementally builds the solution and backtracks when a partial solution violates the constraints.
HighLevel Steps:
 Initialize an empty chessboard of size $N \times N$.
 Try placing a queen in each column of the first row and check for conflicts.
 Move to the next row.
 For each column, attempt to place a queen.
 Check if the placement is safe (no conflicts with existing queens).
 If no safe position is found in the current row, backtrack to the previous row.
 Try the next available position in the previous row.
 When $N$ queens have been successfully placed without conflicts, record the solution.
 Continue the process to find all possible solutions.
Python Implementation
Below is a Python implementation of the NQueens problem using backtracking.
def solve_n_queens(N):
solutions = []
board = [1] * N # board[row] = column position of queen in that row
def is_safe(row, col):
for prev_row in range(row):
# Check column conflict
if board[prev_row] == col:
return False
# Check diagonal conflicts
if abs(board[prev_row]  col) == abs(prev_row  row):
return False
return True
def place_queen(row):
if row == N:
# All queens are placed successfully
solutions.append(board.copy())
return
for col in range(N):
if is_safe(row, col):
board[row] = col # Place queen
place_queen(row + 1) # Move to next row
board[row] = 1 # Backtrack
place_queen(0)
return solutions
# Example usage
N = 4
solutions = solve_n_queens(N)
print(f"Number of solutions for N={N}: {len(solutions)}")
for index, sol in enumerate(solutions):
print(f"\nSolution {index + 1}:")
for row in range(N):
line = ['.'] * N
if sol[row] != 1:
line[sol[row]] = 'Q'
print(' '.join(line))
Execution Flow
 Try placing a queen in columns
0
toN  1
.  For each valid placement, proceed to row
1
.  At each row, attempt to place a queen in a safe column.
 If no safe column is found, backtrack to the previous row.
 When a valid placement is found for all $N$ rows, record the solution.
All Solutions for $N = 4$
There are two distinct solutions for $N = 4$:
Solution 1:
Board Representation: [1, 3, 0, 2]
0 1 2 3
+++++
0  Q   
+++++
1    Q 
+++++
2 Q    
+++++
3   Q  
+++++
Solution 2:
Board Representation: [2, 0, 3, 1]
0 1 2 3
+++++
0   Q  
+++++
1 Q    
+++++
2    Q 
+++++
3  Q   
+++++
Output of the Program
Number of solutions for N=4: 2
Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .
Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .
Visualization of the Backtracking Tree
The algorithm explores the solution space as a tree, where each node represents a partial solution (queens placed up to a certain row). The branches represent the possible positions for the next queen.
 Nodes represent partial solutions where a certain number of queens have already been placed in specific rows.
 Branches correspond to the possible positions for placing the next queen in the following row, exploring each valid option.
 Leaves are the complete solutions when all $N$ queens have been successfully placed on the board without conflicts.
The backtracking occurs when a node has no valid branches (no safe positions in the next row), prompting the algorithm to return to the previous node and try other options.
Analysis
I. The time complexity of the NQueens problem is $O(N!)$ as the algorithm explores permutations of queen placements across rows.
II. The space complexity is $O(N)$, where:
 The
board
array stores the positions of the $N$ queens.  The recursion stack can go as deep as $N$ levels during the backtracking process.
Applications
 Constraint satisfaction problems often use the NQueens problem as a classic example to study and develop solutions for placing constraints on variable assignments.
 In algorithm design, the NQueens problem helps illustrate the principles of backtracking and recursive problemsolving.
 In artificial intelligence, it serves as a foundational example for search algorithms and optimization techniques.
Potential Improvements
 Implementing more efficient conflict detection methods.
 Using heuristics to choose the order of columns to try first.
 Converting the recursive solution to an iterative one using explicit stacks to handle larger values of $N$ without stack overflow.
Example: Maze Solver
Given a maze represented as a 2D grid, find a path from the starting point to the goal using backtracking. The maze consists of open paths and walls, and movement is allowed in four directions: up, down, left, and right (no diagonal moves). The goal is to determine a sequence of moves that leads from the start to the goal without crossing any walls.
Maze Representation
Grid Cells:
.
(dot) represents an open path.#
(hash) represents a wall or obstacle.
Allowed Moves:
 Up, down, left, right.
 No diagonal movement.
ASCII Representation
Let's visualize the maze using ASCII graphics to better understand the problem.
Maze Layout:
Start (S) at position (0, 0)
Goal (G) at position (5, 5)
0 1 2 3 4 5 (Columns)
0 S . # . . .
1 . # . . . .
2 . . . . # .
3 . # # # . .
4 . . . # . .
5 # # # # . G
Legend:
S  Start
G  Goal
.  Open path
#  Wall
Here's the maze grid with indices:
0 1 2 3 4 5
+++++++
0  S  .  #  .  .  . 
+++++++
1  .  #  .  .  .  . 
+++++++
2  .  .  .  .  #  . 
+++++++
3  .  #  #  #  .  . 
+++++++
4  .  .  .  #  .  . 
+++++++
5  #  #  #  #  .  G 
+++++++
Objective:
Find a sequence of moves from S
to G
, navigating only through open paths (.
) and avoiding walls (#
). The path should be returned as a list of grid coordinates representing the steps from the start to the goal.
Python Implementation
def solve_maze(maze, start, goal):
rows, cols = len(maze), len(maze[0])
path = []
def is_valid(x, y):
return (0 <= x < rows and 0 <= y < cols and maze[x][y] == '.')
def explore(x, y):
if not is_valid(x, y):
return False
if (x, y) == goal:
path.append((x, y))
return True
maze[x][y] = 'V' # Mark as visited
path.append((x, y))
# Try all possible directions: down, up, right, left
if (explore(x + 1, y) or
explore(x  1, y) or
explore(x, y + 1) or
explore(x, y  1)):
return True
path.pop() # Backtrack
maze[x][y] = '.' # Unmark visited
return False
if explore(*start):
return path
else:
return None
# Sample maze (as a list of lists)
maze = [
['.', '.', '#', '.', '.', '.'],
['.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.'],
['.', '#', '#', '#', '.', '.'],
['.', '.', '.', '#', '.', '.'],
['#', '#', '#', '#', '.', '.']
]
start = (0, 0)
goal = (5, 5)
solution = solve_maze(maze, start, goal)
if solution:
print("Path to goal:")
for step in solution:
print(step)
else:
print("No path found.")
Recursive Function explore(x, y)
I. Base Cases:
 If
(x, y)
is not valid (out of bounds, wall, or visited), returnFalse
.  If
(x, y)
equals the goal position, append it topath
and returnTrue
.
II. Recursive Exploration:
 Mark the current cell
(x, y)
as visited by settingmaze[x][y] = 'V'
.  Append
(x, y)
to thepath
.  Recursively attempt to explore neighboring cells in the following order:
 Move Down:
explore(x + 1, y)
 Move Up:
explore(x  1, y)
 Move Right:
explore(x, y + 1)
 Move Left:
explore(x, y  1)
 If any recursive call returns
True
, propagate theTrue
value upwards.
III. Backtracking:
 If none of the neighboring cells lead to a solution, backtrack:
 Remove
(x, y)
frompath
usingpath.pop()
.  Unmark the cell by setting
maze[x][y] = '.'
.  Return
False
to indicate that this path does not lead to the goal.
Execution Flow
I. Start at (0, 0)
:
 The algorithm begins at the starting position.
 Marks
(0, 0)
as visited and adds it to the path.
II. Explore Neighbors:
 Tries moving Down to
(1, 0)
.
III. Recursive Exploration:
 From
(1, 0)
, continues moving Down to(2, 0)
.  From
(2, 0)
, attempts Right to(2, 1)
.
IV. Dead Ends and Backtracking:
 If a path leads to a wall or visited cell, the algorithm backtracks to the previous cell and tries a different direction.
 This process continues, exploring all possible paths recursively.
V. Reaching the Goal:
 Eventually, the algorithm reaches the goal
(5, 5)
if a path exists.  The function returns
True
, and the full path is constructed via the recursive calls.
Output
 If a path is found, it prints "Path to goal:" followed by the list of coordinates in the path.
 If no path exists, it prints "No path found."
Final Path Found
The path from start to goal:
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3),
(1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (4, 5),
(5, 5)]
Visual Representation of the Path
Let's overlay the path onto the maze for better visualization. We'll use *
to indicate the path.
Maze with Path:
0 1 2 3 4 5
+++++++
0  *  *  #  .  .  . 
+++++++
1  *  #  .  *  *  * 
+++++++
2  *  *  *  *  #  * 
+++++++
3  .  #  #  #  .  * 
+++++++
4  .  .  .  #  .  * 
+++++++
5  #  #  #  #  .  * 
+++++++
Legend:
*  Path taken
#  Wall
.  Open path
Advantages of Using Backtracking for Maze Solving
 Ensures that all possible paths are explored until the goal is found.
 Only the current path and visited cells are stored, reducing memory usage compared to storing all possible paths.
 Recursive implementation leads to clean and understandable code.
Potential Improvements
 This algorithm finds a path but not necessarily the shortest path.
 To find the shortest path, algorithms like BreadthFirst Search (BFS) are more suitable.
 Modify the code to collect all possible paths by removing early returns when the goal is found.
 Allowing diagonal movements would require adjusting the
explore
function to include additional directions.
List of Problems
Permutations
Develop an algorithm to generate all possible permutations of a given list of elements. This problem requires creating different arrangements of the elements where the order matters.
Combinations
Design an algorithm to generate all possible combinations of 'k' elements selected from a given list of elements. This involves selecting elements where the order does not matter, but the selection size does.
String Pattern
Create a solution to determine whether a given string adheres to a specified pattern, where the pattern may include letters and wildcard characters that represent any character. This problem often involves checking for matches and handling special pattern symbols.
Generating Words
Generate all possible words that can be formed from a given list of characters and match a specified pattern. The pattern can contain letters and wildcard characters, requiring the algorithm to account for flexible matching.
Hamiltonian Path
Create an algorithm that identifies whether a simple path exists within a provided undirected or directed graph. This path should visit every vertex exactly once. Known as the "traveling salesman problem," it can be addressed using depthfirst search to explore possible paths.
KColorable Configurations
Develop an algorithm to find all possible ways to color a given graph with 'k' colors such that no two adjacent vertices share the same color. This graph coloring problem requires ensuring valid color assignments for all vertices.
Knight Tour
Create an algorithm to find all potential paths a knight can take on an 'n' x 'n' chessboard to visit every square exactly once. This classic chess problem involves ensuring the knight moves in an Lshape and covers all board positions.
Topological Orderings
Determine a topological ordering of the vertices in a given directed graph, if one exists. This involves sorting the vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering.
TicTacToe (Minimax)
Develop an algorithm to determine the optimal move for a player in a game of tictactoe using the minimax algorithm. This requires evaluating possible moves to find the best strategy for winning or drawing the game.