Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your...

  
 

Transcribed Image Text:

Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your program, solve the three puzzles given in Section 5.3.3. 5.3.3 Multiple Recursion Generalizing from binary recursion, we define multiple recursion as a process in which a method may make more than two recursive calls. Our recursion for an- alyzing the disk space usage of a file system (see Section 5.1.4) is an example of multiple recursion, because the number of recursive calls made during one invoca- tion was equal to the number of entries within a given directory of the file system. Another common application of multiple recursion is when we want to enumer- ate various configurations in order to solve a combinatorial puzzle. For example, the following are all instances of what are known as summation puzzles: pot + pan dog + cat boy + girl bib pig baby To solve such a puzzle, we need to assign a unique digit (that is, 0, 1.....9) to each letter in the equation, in order to make the equation true. Typically, we solve such a puzzle by using our human observations of the particular puzzle we are trying to solve to eliminate configurations (that is, possible partial assignments of digits to letters) until we can work through the feasible configurations that remain, testing for the correctness of each one. If the number of possible configurations is not too large, however, we can use a computer to simply enumerate all the possibilities and test each one, without em- ploying any human observations. Such an algorithm can use multiple recursion to work through the configurations in a systematic way. To keep the description general enough to be used with other puzzles, we consider an algorithm that enu- merates and tests all k-length sequences, without repetitions, chosen from a given universe U. We show pseudocode for such an algorithm in Code Fragment 5.11. building the sequence of k elements with the following steps: Recursively generating the sequences of k 1 elements 2. Appending to each such sequence an element not already contained in it. Throughout the execution of the algorithm, we use a set U to keep track of the elements not contained in the current sequence, so that an element e has not been used yet if and only if e is in U. Another way to look at the algorithm of Code Fragment 5.11 is that it enumer- ates every possible size-k ordered subset of U, and tests each subset for being a possible solution to our puzzle. For summation puzzles. U (0.1.2.3.4.5.6.7.8.9) and each position in the sequence corresponds to a given letter. For example, the first position could stand for b, the second for o, the third for y, and so on. Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U if k== 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output (a solution) (a recursive call) (e is now considered as unused) Code Fragment 5.11: Solving a combinatorial puzzle by enumerating and testing all possible configurations. else PuzzleSolve (k - I, S, U) Remove e from the end of S Add e back to U In Figure 5.14, we show a recursion trace of a call to PuzzleSolve(3, S, U), where S is empty and U= (a,b,c). During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3, S, U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 5.14. PuzzleSolve(2, a. (b.c)) PuzzleSolve(Lab. (c)) initial call PuzzleSolvet), () [ab.c)) PuzzleSolve(2, b. Jac))) PuraleSolvr(1, ba, (c)) (e is now being used) PuraleSolve(, {b]] PuzzleSolve(2. < [a,bl) PuzzleSahver(1, ca. [b]) PuzzleSolve(t bc. 1H PizaleSolve( cb. (a)), chu Figure 5.14: Recursion trace for an execution of PuzzleSolve(3, S. U), where Sis empty and 7-a.b.c). This execution generates and tests all permutations of a, b, and c. We show the permutations generated directly below their respective boxes. Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your program, solve the three puzzles given in Section 5.3.3. 5.3.3 Multiple Recursion Generalizing from binary recursion, we define multiple recursion as a process in which a method may make more than two recursive calls. Our recursion for an- alyzing the disk space usage of a file system (see Section 5.1.4) is an example of multiple recursion, because the number of recursive calls made during one invoca- tion was equal to the number of entries within a given directory of the file system. Another common application of multiple recursion is when we want to enumer- ate various configurations in order to solve a combinatorial puzzle. For example, the following are all instances of what are known as summation puzzles: pot + pan dog + cat boy + girl bib pig baby To solve such a puzzle, we need to assign a unique digit (that is, 0, 1.....9) to each letter in the equation, in order to make the equation true. Typically, we solve such a puzzle by using our human observations of the particular puzzle we are trying to solve to eliminate configurations (that is, possible partial assignments of digits to letters) until we can work through the feasible configurations that remain, testing for the correctness of each one. If the number of possible configurations is not too large, however, we can use a computer to simply enumerate all the possibilities and test each one, without em- ploying any human observations. Such an algorithm can use multiple recursion to work through the configurations in a systematic way. To keep the description general enough to be used with other puzzles, we consider an algorithm that enu- merates and tests all k-length sequences, without repetitions, chosen from a given universe U. We show pseudocode for such an algorithm in Code Fragment 5.11. building the sequence of k elements with the following steps: Recursively generating the sequences of k 1 elements 2. Appending to each such sequence an element not already contained in it. Throughout the execution of the algorithm, we use a set U to keep track of the elements not contained in the current sequence, so that an element e has not been used yet if and only if e is in U. Another way to look at the algorithm of Code Fragment 5.11 is that it enumer- ates every possible size-k ordered subset of U, and tests each subset for being a possible solution to our puzzle. For summation puzzles. U (0.1.2.3.4.5.6.7.8.9) and each position in the sequence corresponds to a given letter. For example, the first position could stand for b, the second for o, the third for y, and so on. Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U if k== 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output (a solution) (a recursive call) (e is now considered as unused) Code Fragment 5.11: Solving a combinatorial puzzle by enumerating and testing all possible configurations. else PuzzleSolve (k - I, S, U) Remove e from the end of S Add e back to U In Figure 5.14, we show a recursion trace of a call to PuzzleSolve(3, S, U), where S is empty and U= (a,b,c). During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3, S, U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 5.14. PuzzleSolve(2, a. (b.c)) PuzzleSolve(Lab. (c)) initial call PuzzleSolvet), () [ab.c)) PuzzleSolve(2, b. Jac))) PuraleSolvr(1, ba, (c)) (e is now being used) PuraleSolve(, {b]] PuzzleSolve(2. < [a,bl) PuzzleSahver(1, ca. [b]) PuzzleSolve(t bc. 1H PizaleSolve( cb. (a)), chu Figure 5.14: Recursion trace for an execution of PuzzleSolve(3, S. U), where Sis empty and 7-a.b.c). This execution generates and tests all permutations of a, b, and c. We show the permutations generated directly below their respective boxes.