Backtracking

A recursive strategy.

How

• Choose, for the current step
• Explore, Recusively try to solve the remaining problem with the current choice
• Backtracking, If the choice lead to an invalid solution, undo it and try another option
• Base Case: stop when a solution is found or all options are exhausted

Why

• Depth-First Search Explores one path fully before backtracking.
• Pruncing Early valitions for option avoids exploring invalid paths