Last modified: August 31, 2025
This article is written in: 🇺🇸
Backtracking is a method used to solve problems by building potential solutions step by step. If it becomes clear that a partial solution cannot lead to a valid final solution, the process "backtracks" by undoing the last step and trying a different path. This approach is commonly applied to constraint satisfaction problems, combinatorial optimization, and puzzles like N-Queens or Sudoku, where all possibilities need to be explored systematically while avoiding unnecessary computations.
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:
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:
The factorial of a non-negative 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
Let's trace the recursive calls for factorial(5)
:
factorial(5)
and compute $5 \times factorial(4)$ because $5 \neq 0$. factorial(4)
and compute $4 \times factorial(3)$. factorial(3)
and compute $3 \times factorial(2)$. factorial(2)
and compute $2 \times factorial(1)$. factorial(1)
and compute $1 \times factorial(0)$. factorial(0)
and return $1$ as the base case is reached. 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$.
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:
Depth-First 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:
Pseudocode:
DFS(node):
mark node as visited
for each neighbor in node.neighbors:
if neighbor is not visited:
DFS(neighbor)
Consider the following tree:
Tree:
A
/ \
B C
/ \
D E
Traversal using DFS starting from node 'A':
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:
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:
General Template (pseudocode)
function backtrack(partial):
if is_complete(partial):
handle_solution(partial)
return // or continue if looking for all solutions
for candidate in generate_candidates(partial):
if is_valid(candidate, partial):
place(candidate, partial) // extend partial with candidate
backtrack(partial)
unplace(candidate, partial) // undo extension (backtrack)
Pieces you supply per problem:
is_complete
: does partial
represent a full solution?handle_solution
: record/output the solution.generate_candidates
: possible next choices given current partial.is_valid
: pruning test to reject infeasible choices early.place
/ unplace
: apply and revert the choice.Python-ish Generic Framework
def backtrack(partial, is_complete, generate_candidates, is_valid, handle_solution):
if is_complete(partial):
handle_solution(partial)
return
for candidate in generate_candidates(partial):
if not is_valid(candidate, partial):
continue
# make move
partial.append(candidate)
backtrack(partial, is_complete, generate_candidates, is_valid, handle_solution)
# undo move
partial.pop()
You can wrap those callbacks into a class or closures for stateful problems.
The N-Queens 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:
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.Backtracking is an ideal algorithmic approach for solving the N-Queens problem due to its constraint satisfaction nature. The algorithm incrementally builds the solution and backtracks when a partial solution violates the constraints.
High-Level Steps:
Below is a Python implementation of the N-Queens 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))
0
to N - 1
.1
.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 | | |
+---+---+---+---+
Number of solutions for N=4: 2
Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .
Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .
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.
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.
I. The time complexity of the N-Queens problem is $O(N!)$ as the algorithm explores permutations of queen placements across rows.
II. The space complexity is $O(N)$, where:
board
array stores the positions of the $N$ queens.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.
Grid Cells:
.
(dot) represents an open path.#
(hash) represents a wall or obstacle.Allowed Moves:
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.
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.")
explore(x, y)
I. Base Cases:
(x, y)
is not valid (out of bounds, wall, or visited), return False
.(x, y)
equals the goal position, append it to path
and return True
.II. Recursive Exploration:
(x, y)
as visited by setting maze[x][y] = 'V'
.(x, y)
to the path
.explore(x + 1, y)
explore(x - 1, y)
explore(x, y + 1)
explore(x, y - 1)
True
, propagate the True
value upwards.III. Backtracking:
(x, y)
from path
using path.pop()
.maze[x][y] = '.'
.False
to indicate that this path does not lead to the goal.I. Start at (0, 0)
:
(0, 0)
as visited and adds it to the path.II. Explore Neighbors:
(1, 0)
.III. Recursive Exploration:
(1, 0)
, continues moving Down to (2, 0)
.(2, 0)
, attempts Right to (2, 1)
.IV. Dead Ends and Backtracking:
V. Reaching the Goal:
(5, 5)
if a path exists.True
, and the full path is constructed via the recursive calls.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)]
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
explore
function to include additional directions.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.
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.
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.
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.
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 depth-first search to explore possible paths.
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.
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 L-shape and covers all board positions.
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.
Develop an algorithm to determine the optimal move for a player in a game of tic-tac-toe using the minimax algorithm. This requires evaluating possible moves to find the best strategy for winning or drawing the game.