18. Backtracking

🧸 ELI5: You're solving a maze (or a Sudoku puzzle). You try a path. If it leads to a dead end, you walk back (backtrack) to your last choice and try a different path instead. You keep exploring and undoing until you find a path that works — or discover none exist.

🌍 Real life: Solving a Sudoku puzzle — try a number, if it breaks a rule later, erase it and try the next number. Solving a maze on paper with a pencil, backing up when you hit a wall. A GPS trying alternate routes when one turns out to be blocked.

📝 Pseudocode (N-Queens style: place items without conflicts):

function solve(board, row):
    if row == size(board): return true    // all placed successfully!
    for col in 0..size(board):
        if isSafe(board, row, col):
            place(board, row, col)         // try it
            if solve(board, row + 1): return true
            remove(board, row, col)        // backtrack — undo and try next
    return false                            // no option worked from here

🐹 Go (N-Queens: place N queens on a chessboard so none attack each other):

package main

import "fmt"

func isSafe(cols []int, row, col int) bool {
	for r := 0; r < row; r++ {
		c := cols[r]
		if c == col || r-c == row-col || r+c == row+col {
			return false // same column or same diagonal — queens attack!
		}
	}
	return true
}

func solve(cols []int, row, n int) bool {
	if row == n {
		return true // placed every queen safely
	}
	for col := 0; col < n; col++ {
		if isSafe(cols, row, col) {
			cols[row] = col       // try placing the queen here
			if solve(cols, row+1, n) {
				return true
			}
			// backtrack is implicit: next loop iteration overwrites cols[row]
		}
	}
	return false // dead end — go back further
}

func main() {
	n := 4
	cols := make([]int, n)
	if solve(cols, 0, n) {
		fmt.Println("Queen positions (row -> col):", cols)
	}
}

🇨 C — line for line the same recursion as the Go version; backtracking here is literally "the loop moves to its next iteration and overwrites cols[row]," with no explicit "undo" step needed:

#include <stdio.h>

int is_safe(const int *cols, int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = cols[r];
        if (c == col || r - c == row - col || r + c == row + col) return 0; // same column or diagonal
    }
    return 1;
}

int solve(int *cols, int row, int n) {
    if (row == n) return 1;               // placed every queen safely
    for (int col = 0; col < n; col++) {
        if (is_safe(cols, row, col)) {
            cols[row] = col;               // try placing the queen here
            if (solve(cols, row + 1, n)) return 1;
            // backtrack is implicit: next loop iteration overwrites cols[row]
        }
    }
    return 0;                               // dead end — go back further
}

int main(void) {
    int n = 4;
    int cols[4];
    if (solve(cols, 0, n)) {
        printf("Queen positions (row -> col):");
        for (int i = 0; i < n; i++) printf(" %d", cols[i]);
        printf("\n");
    }
    return 0;
}

⏱️ Complexity: Often exponential in the worst case (O(kⁿ)-ish) — but backtracking prunes dead ends early, so it's much faster in practice than trying every possibility blindly.