10-recursive-backtracking

Unit 10: Complete search - recursive backtracking

This unit covers the complete search paradigm, with a focus on recursive backtracking (pruning and usage of bitmasks is included).

Complementary notes can be found in sections 3.2.2 and 8.2.1 of the book Competitive Programming 3.

Prerequisites

• Unit 1: Complexity
• Unit 2: Linear data structures

Practice problems

Iterative complete search

• UVa 441 - Lotto
• UVa 471 - Magic Numbers
• UVa 188 - Perfect Hash
• UVa 161 - Traffic Lights

Recursive backtracking

Easy

• UVa 750 - 8 Queens Chess Problem
• UVa 10276 - Hanoi Tower Troubles Again!
• UVa 677 - All Walks of length n from the first node

Medium

• UVa 574 - Sum it up
• UVa 10950 - Bad Code
• UVa 11961 - DNA

Harder

• UVa 208 - Firetruck
• UVa 861 - Little Bishops
• UVa 868 - Numerical maze
• UVa 193 - Graph coloring