• i. Backtracking and Pruning: enumeration templates, pruning heuristics, N-Queens and knight’s-tour bitmask search, and a real backtracking Sudoku/maze/word-search solver.
• ii. Meet in the Middle: splitting the input in half for subset-sum-style problems, and bidirectional search as its graph analogue.
• iii. A*, IDA* and Branch and Bound: A* with its admissibility proof, IDA* for memory-bound state spaces, and the 15-puzzle’s solvability invariant.
• iv. Exact Cover and Dancing Links: modelling a problem as exact cover (Sudoku, N-Queens, polyomino tiling) and a tested array-based DLX implementation.
• v. Maximum Clique and Independent Set: the tractable special cases, Bron-Kerbosch with pivoting and bitsets, and the colouring bound for branch and bound.
• vi. Satisfiability: the 2-SAT/3-SAT complexity cliff, Horn-SAT and XOR-SAT tractability, encoding recipes, and the binary-search-plus-2-SAT pattern.
• vii. Steiner Tree: the exact Dreyfus-Wagner subset DP, the metric-closure 2-approximation, and the exact solution when the graph is a tree.