Exercise 3: Why Only One of the Two Searches Is "Exhaustive" — Possible Solution ==================================================================== WHAT "CHECKING EVERY POSSIBILITY" MEANS IN EACH CASE ------------------------------ Both algorithms are guaranteed to find a correct answer if one exists, within the specific set of candidates each one is actually built to consider - in that limited sense, both are complete, reliable searches, and neither one would report "no solution" when a valid solution genuinely exists (as long as the backtracking version's pruning rule is valid, per Exercise 2's own finding about what happens when it isn't). WHY BRUTE FORCE IS SPECIFICALLY "EXHAUSTIVE" IN CHAPTER 6'S SENSE ------------------------------ Chapter 6 used "exhaustive" to describe an algorithm that builds and checks every single FULLY-FORMED candidate individually, with no candidate ever skipped or excluded before being completely examined - all 1,024 subsets get generated and checked, regardless of whether some of them could have been ruled out earlier. This chapter's own comparison table captured this directly: brute force "builds candidates all at once, fully formed" and "rejects a bad candidate only after it's fully built and checked." WHY BACKTRACKING IS NOT DESCRIBED THE SAME WAY ------------------------------ Backtracking never fully constructs the vast majority of the 1,024 possible subsets at all - the moment a PARTIAL candidate (not yet a complete subset) is proven hopeless, that whole branch of possibilities is abandoned without ever generating the complete candidates that would have grown from it. This chapter's own verified count - 22 nodes explored instead of 1,024 - is direct evidence that backtracking is examining a genuinely smaller set of things than "every possible subset," even though it still reliably finds a correct answer whenever one exists. Calling this "exhaustive" in Chapter 6's specific sense would be misleading, since the entire point of backtracking is to avoid exhaustively generating every candidate. THE ACTUAL DISTINGUISHING PROPERTY ------------------------------ The key difference isn't "does it find the right answer" (both do, given a valid pruning rule) - it's "does it examine every possible FULL candidate, or does it eliminate many of them in bulk before they're ever fully formed." Brute force does the former; backtracking specifically avoids it, which is exactly why this chapter introduced it as a genuine alternative to exhaustive search rather than just a faster implementation of the same idea. WHY THIS WORKS AS AN ANSWER ------------------------------ The answer identifies what the two approaches genuinely share (reliably finding a correct answer within their own candidate space) before precisely defining Chapter 6's own specific meaning of "exhaustive" and showing, using this chapter's own verified 22-vs-1,024 node count, why backtracking doesn't fit that definition even though it is just as reliable.