Pruning: Backtracking with Constraints

The subsets and permutations from the last module never had to reject a choice mid-search - every partial path was automatically valid. Most real backtracking problems are not that forgiving: they come with constraints that a partial solution can violate long before it is complete, and the trick that makes them practical is pruning - checking the constraint the instant a choice is made, and refusing to recurse any further down a branch that is already doomed.

N-Queens asks: on an n×n chessboard, how many ways can you place n queens so that no two attack each other? Two queens attack each other if they share a row, a column, or a diagonal. A useful simplification: since no two queens can ever share a row, you can place exactly one queen per row and only need to decide which column each row's queen goes in - turning the search into "try every column for row 0, then every column for row 1, ..." rather than reasoning about the whole board's worth of row choices at once.

A naive brute force would place a queen in every possible column of every row - generating the full n^n set of column choices - and only check whether the *entire* board is valid at the very end. Almost all of that work is wasted: if row 2's queen already conflicts with row 0's queen, nothing that happens in rows 3 through n-1 can fix it, yet the naive approach still generates every combination of those later rows before ever noticing the problem.

Pruning fixes this by checking each new queen against every queen already placed before recursing to the next row - reject immediately instead of generating the full board first. A column conflict is easy: track which columns are already occupied in a set. Diagonals need one observation each: every cell on the same "\" diagonal (top-left to bottom-right) shares the same value of row - col, and every cell on the same "/" diagonal (top-right to bottom-left) shares the same value of row + col. Tracking both of those differences in their own sets catches every diagonal conflict in O(1) per check.

Notice the shape is identical to the subsets/permutations template - choose, explore, un-choose - with exactly one addition: an `if` check before the choose step that skips the entire iteration (and everything it would have recursed into) when a conflict is detected. That single check is what separates "backtracking" from "brute force with a backtracking-shaped loop."

• -Pruning does not change the theoretical worst-case complexity of the search - N-Queens is still exponential in the worst case.
• -What pruning changes is how much of the exponential search tree actually gets explored: invalid branches are cut off after one row instead of after all n rows.
• -The same idea - "check the constraint as early as possible, one decision at a time" - generalizes to Sudoku, graph coloring, and any other constraint-satisfaction search.