Backtracking from Scratch (2026)
Backtracking is a systematic algorithm for finding all (or some) solutions to computational problems by building candidates incrementally and abandoning candidates as soon as we determine they cannot lead to a valid solution. It is the algorithmic equivalent of trial and error, exploring the solution space with pruning to avoid unnecessary exploration.
In this tutorial, we will implement classic backtracking problems including N-Queens, Sudoku Solver, Subset Sum, and Hamiltonian Cycle. We will understand the backtracking template, learn pruning strategies, and analyze the time complexity of backtracking algorithms.
N-Queens Problem
The N-Queens problem asks us to place N queens on an N x N chessboard such that no two queens threaten each other (no two queens share the same row, column, or diagonal). We place queens row by row, checking if each position is safe. If we find a dead end (no safe position in a row), we backtrack to the previous row and try the next position.
The algorithm tries placing a queen in each column of the current row. If the position is safe, we recursively place queens in the next row. If we successfully place all N queens, we have found a solution.
def solve_n_queens(n):
def is_safe(board, row, col):
for i in range(row):
if board[i][col] == 1: return False
for i, j in zip(range(row-1,-1,-1), range(col-1,-1,-1)):
if board[i][j] == 1: return False
for i, j in zip(range(row-1,-1,-1), range(col+1,n)):
if board[i][j] == 1: return False
return True
def solve(board, row):
if row == n:
solutions.append([r[:] for r in board])
return
for col in range(n):
if is_safe(board, row, col):
board[row][col] = 1
solve(board, row + 1)
board[row][col] = 0
solutions = []
board = [[0]*n for _ in range(n)]
solve(board, 0)
return solutions
for sol in solve_n_queens(4):
for row in sol: print(''.join('Q' if x else '.' for x in row))
print()Sudoku Solver
Sudoku is a classic backtracking problem. Given a 9x9 grid with some cells filled, we must fill the remaining cells such that each row, column, and 3x3 box contains digits 1-9 exactly once. We try each digit in empty cells, check if it's valid (not violating Sudoku rules), and recursively solve the rest. If no digit works, we backtrack.
The algorithm finds the next empty cell, tries digits 1-9, validates the placement, and recursively continues. This is a direct application of the backtracking template.
#include
#include
using namespace std;
bool isValid(vector>& board, int row, int col, int num) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == num) return false;
if (board[i][col] == num) return false;
int br = 3*(row/3)+i/3, bc = 3*(col/3)+i%3;
if (board[br][bc] == num) return false;
}
return true;
}
bool solveSudoku(vector>& board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == 0) {
for (int num = 1; num <= 9; num++) {
if (isValid(board, r, c, num)) {
board[r][c] = num;
if (solveSudoku(board)) return true;
board[r][c] = 0;
}
}
return false;
}
}
}
return true;
} Subset Sum Problem
The subset sum problem asks whether there exists a subset of a given set that sums to a target value. This is a classic NP-complete problem that can be solved efficiently with backtracking for small inputs. We make a decision for each element: include it or exclude it, building the subset incrementally.
The backtracking approach explores two branches for each element: include it (subtract from target) or exclude it. We prune branches where the remaining target becomes negative or when the sum of remaining elements is insufficient.
import java.util.*;
public class SubsetSum {
static void subsetSum(int[] arr, int target, int index,
List current, List> results) {
if (target == 0) { results.add(new ArrayList<>(current)); return; }
if (index >= arr.length || target < 0) return;
current.add(arr[index]);
subsetSum(arr, target - arr[index], index + 1, current, results);
current.remove(current.size() - 1);
subsetSum(arr, target, index + 1, current, results);
}
public static void main(String[] args) {
int[] arr = {2, 3, 6, 7};
List> results = new ArrayList<>();
subsetSum(arr, 9, 0, new ArrayList<>(), results);
for (List s : results) System.out.println(s);
}
} Hamiltonian Cycle
A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex. Finding a Hamiltonian cycle is NP-complete, but backtracking can solve it for small graphs. We start at vertex 0, try to extend the path by visiting an unvisited adjacent vertex, and backtrack when no unvisited neighbor exists.
The algorithm maintains a path array and a visited set. For each vertex, we try all unvisited neighbors. If we reach a vertex with no unvisited neighbors, we backtrack. If all vertices are visited and there is an edge back to the start, we have found a Hamiltonian cycle.
def hamiltonian_cycle(graph, n):
path = [-1] * n
path[0] = 0
def is_safe(v, pos):
if not graph[path[pos - 1]][v]: return False
if v in path[:pos]: return False
return True
def solve(pos):
if pos == n: return graph[path[pos-1]][path[0]]
for v in range(1, n):
if is_safe(v, pos):
path[pos] = v
if solve(pos + 1): return True
path[pos] = -1
return False
if solve(1): return path + [path[0]]
return None
graph = [
[0,1,0,1,0], [1,0,1,1,1], [0,1,0,0,1],
[1,1,0,0,1], [0,1,1,1,0]
]
cycle = hamiltonian_cycle(graph, 5)
print("Hamiltonian Cycle:", cycle if cycle else "None")Frequently Asked Questions
What is backtracking?
Backtracking is a systematic search algorithm that builds candidates incrementally and prunes branches that cannot lead to valid solutions. It is the algorithmic equivalent of trial and error with early termination.
When to use backtracking?
Use backtracking for constraint satisfaction problems, combinatorial optimization, finding all solutions, and problems where we build candidates and check validity: N-Queens, Sudoku, subset sum, permutations.
How to improve backtracking performance?
Add pruning to eliminate invalid branches early. Use constraint propagation. Order choices heuristically. Use memoization for overlapping subproblems. Convert to dynamic programming when applicable.
What is the time complexity of backtracking?
Backtracking is generally exponential: O(b^d) where b is the branching factor and d is the depth. Pruning reduces the effective branching factor. For NP-complete problems, there is no polynomial solution known.
Originally published on Ayodhyyya. Last updated June 1, 2026.