PPT Slide
Eventually, it backtracks all the way to the third node where the
program stops. Do you see why it isn’t necessary to backtrack to the first point to try all of the possibilities there?
Notes:
Starting at 0000, the first four choices are equivalent, so we don’t need to try them all; one is sufficient. Similar reasoning lets us to stop searching when we backtrack to the point where 1,2,3 changes to 1,2,4 since they are equivalent.