Backtracking

What is Backtracking?

Backtracking is a systematic method for solving constraint satisfaction problems. It builds a solution incrementally and abandons (backtracks) a partial solution as soon as it determines that it cannot lead to a valid complete solution.

Think of it as a depth-first search through a decision tree, with pruning to cut off branches that can't lead to a solution.

Choose â€” make a choice (place a queen, assign a color)
Explore â€” recursively explore with that choice
Unchoose â€” if the choice leads to failure, undo it and try the next option

N-Queens Problem

Place N queens on an NÃ—N chessboard so that no two queens attack each other (no two queens share the same row, column, or diagonal).

N-Queens Problem

public class NQueens {

    static int n;
    static int[] board;  // board[row] = column of queen in that row
    static int solutions = 0;

    static boolean isSafe(int row, int col) {
        for (int r = 0; r < row; r++) {
            if (board[r] == col) return false;  // same column
            if (Math.abs(board[r] - col) == Math.abs(r - row)) return false;  // diagonal
        }
        return true;
    }

    static void solve(int row) {
        if (row == n) {
            solutions++;
            printBoard();
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;    // CHOOSE: place queen
                solve(row + 1);      // EXPLORE
                board[row] = -1;     // UNCHOOSE: remove queen (backtrack)
            }
        }
    }

    static void printBoard() {
        System.out.println("Solution " + solutions + ":");
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                System.out.print(board[r] == c ? "Q " : ". ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        n = 4;
        board = new int[n];
        java.util.Arrays.fill(board, -1);
        solve(0);
        System.out.println("Total solutions for " + n + "-Queens: " + solutions);
        // 4-Queens has 2 solutions
    }
}

Subset Sum Problem

import java.util.ArrayList;
import java.util.List;

public class SubsetSum {

    // Find all subsets that sum to target
    static void findSubsets(int[] arr, int target, int idx,
                            int currentSum, List<Integer> current) {
        if (currentSum == target) {
            System.out.println("Found: " + current);
            return;
        }
        if (idx == arr.length || currentSum > target) return;  // prune

        // CHOOSE: include arr[idx]
        current.add(arr[idx]);
        findSubsets(arr, target, idx + 1, currentSum + arr[idx], current);

        // UNCHOOSE: exclude arr[idx] (backtrack)
        current.remove(current.size() - 1);
        findSubsets(arr, target, idx + 1, currentSum, current);
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2, 2};
        int target = 6;
        System.out.println("Subsets summing to " + target + ":");
        findSubsets(arr, target, 0, 0, new ArrayList<>());
        // Found: [3, 1, 2]
        // Found: [3, 1, 2]
        // Found: [4, 2]
        // Found: [4, 2]
        // Found: [2, 2, 2] â€” if arr had three 2s
    }
}

Rat in a Maze

Find all paths from the top-left to the bottom-right of a grid, where 1 = open cell and 0 = blocked. The rat can move right or down.

Rat in a Maze â€” Backtracking

public class RatInMaze {

    static int N;
    static int[][] maze;
    static int[][] solution;
    static int paths = 0;

    // 4 directions: right, down, left, up
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static String[] dir = {"R", "D", "L", "U"};

    static boolean isSafe(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N
            && maze[r][c] == 1 && solution[r][c] == 0;
    }

    static void solve(int r, int c, String path) {
        if (r == N - 1 && c == N - 1) {
            paths++;
            System.out.println("Path " + paths + ": " + path);
            return;
        }

        solution[r][c] = 1;  // CHOOSE: mark as visited

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (isSafe(nr, nc)) {
                solve(nr, nc, path + dir[d]);  // EXPLORE
            }
        }

        solution[r][c] = 0;  // UNCHOOSE: unmark (backtrack)
    }

    public static void main(String[] args) {
        N = 4;
        maze = new int[][]{
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {0, 1, 1, 1}
        };
        solution = new int[N][N];

        System.out.println("All paths from (0,0) to (" + (N-1) + "," + (N-1) + "):");
        solve(0, 0, "");
        System.out.println("Total paths: " + paths);
    }
}

/*
 * Maze:
 * 1 0 0 0
 * 1 1 0 1
 * 0 1 0 0
 * 0 1 1 1
 *
 * Path 1: DDRDRR  (Down, Down, Right, Down, Right, Right)
 */

Backtracking Complexity

Backtracking is generally exponential in the worst case, but pruning can dramatically reduce the actual search space:

Problem	Worst Case	With Pruning
N-Queens	O(N!)	Much less in practice
Subset Sum	O(2⊃n)	O(2⊃n) worst, better with pruning
Permutations	O(n!)	O(n!) â€” must generate all
Sudoku	O(9&sup8;¹)	Milliseconds with constraint propagation
Graph Coloring	O(k⊃n)	Better with forward checking

Backtracking

What is Backtracking?

N-Queens Problem

Rat in a Maze

Backtracking Complexity

Ready to Level Up Your Skills?