Table of Contents

Core Ideas

Backtracking is used to make a sequence of decisions

• @Examples

We make exactly 1 decision at a time.

• @Examples

The new choice needs to satisfy all the constraints of the problem.

• @Examples

$\star$ Strat. The Generic Backtracking Template

All the pseudocode blocks have 2 parameters: problem and state

• problem is the smaller variant of the main problem at the current recursion level.
• state is the effect of the sequence of choices that we already made.
  • This does NOT have to be the literal choices themselves.

Depending on the target of the problem, we have 3 types of backtracking.

Find the First Solution

1. Is the next choice in the in the first working solution?

   function TakeOrSkip_First(problem, state) -> bool:
   		if no more choices:
   			return state == goal state
   		
   		skip_works = TakeOrSkip_First(subproblem, state)
   		take_works = skip_works
   		
   		if next choice is valid:
   			make choice
   			take_works = TakeOrSkip_First(subproblem, state after choice)
   
   		return skip_works or take_works
   

2. Out of all valid choices, which one is the next choice in the first working solution?

   function FindNext_First(problem, state) -> bool:
   		if no more choices:
   			return state == goal state
   	
   		for each valid choice:
   			make choice
   			if FindNext_First(subproblem, state after choice):
   				return true
   			else:
   				undo choice
   
   		return false
   

Find All the Solutions

1. If the next choice is valid, take it and see what happens.

   function TakeOrSkip_All(problem, state):
   	if no more choices:
   		if state == goal state:
   				record state 
   		return
   		
   	// Try to skip
   	TakeOrSkip_All(subproblem, state)
   		
   	// if valid, try to take
   	if next choice is valid:
   		make choice
   		TakeOrSkip_All(subproblem, state after choice)
   		undo choice