(Suggested book reading: Programming Abstractions in C++, Chapter 9)
Today we will talk about recursive backtracking. Backtracking is an algorithmic technique for finding solution(s) by trying partial solutions and then abandoning them if they are not suitable. It is called a "brute force" algorithmic technique, because it just tries all paths until it finds what it wants. Backtracking algorithms are often implemented recursively.
Backtracking problems can often be solved using an algorithm that follows the following general pseudocode:
function Explore(choices): if there are no more choices to make: stop. else: for each available choice C: Choose C. Explore the remaining choices. // <-- recursion! Un-choose C. (backtrack!)
So then, for any given problem, the challenge lies in figuring out what the "choices" are, how to "choose" and "un-choose" them, and so on.
Some examples of problems that can be solved using backtracking are:
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!