In section 2.2, the textbook describes a game played with artificial sweetener packets on an nxn board. We'll call the game Packet Also in the section is a figure with the pseudocode for for a method called PlayAnyGame. In the pseudocode, there are two if-statements and a for-loop.

• The first if-statement states: if player has already won in state X. Describe in English how you would determine that for Packet,
• The second if-statement states: if player has already lost in state X. Describe in English how you would determine that for Packet.
• The for-loop states: for all legal moves X -> Y. Explain what a list of legal moves would be in Packet.

Consider the following simple two-player game played on an nx n square grid with a border of squares; let's call the players Horace Fahlberg-Remsen and Vera Rebaudi.? Each player has n tokens that they move across the board from one side to the other. Horace's tokens start in the left border, one in each row, and move horizontally to the right; symmetrically, Vera's tokens start in the top border, one in each column, and move vertically downward. The players alternate turns. In each of his turns, Horace either moves one of his tokens one step to the right into an empty square, or jumps one of his tokens over exactly one of Vera's tokens into an empty square two steps to the right. If no legal moves or jumps are available, Horace simply passes. Similarly, Vera either moves or jumps one of her tokens downward in each of her turns, unless no moves or jumps are possible. The first player to move all their tokens off the edge of the board wins. (It's not hard to prove that as long as there are tokens on the board, at least one player can legally move, and therefore someone eventually wins.) Figure 2.4. Vera wins the 3 x 3 fake-sugar-packet game. for j PLACEQUEENS(Q[1..n),r): if r=n+1 print Q[1..n] else 1 to n legal TRUE for ir 1 to s 1 if (Q[i]=j) or (Q[i]=j+r-i) or (Q[i]=j-s+i) legal FALSE if legal Q[r]- j PLACEQUEENS(Q[1..n],r+1) (Recursion!>> Figure 2.2. Gauss and Laquire's backtracking algorithm for the n queens problem. Consider the following simple two-player game played on an nx n square grid with a border of squares; let's call the players Horace Fahlberg-Remsen and Vera Rebaudi.? Each player has n tokens that they move across the board from one side to the other. Horace's tokens start in the left border, one in each row, and move horizontally to the right; symmetrically, Vera's tokens start in the top border, one in each column, and move vertically downward. The players alternate turns. In each of his turns, Horace either moves one of his tokens one step to the right into an empty square, or jumps one of his tokens over exactly one of Vera's tokens into an empty square two steps to the right. If no legal moves or jumps are available, Horace simply passes. Similarly, Vera either moves or jumps one of her tokens downward in each of her turns, unless no moves or jumps are possible. The first player to move all their tokens off the edge of the board wins. (It's not hard to prove that as long as there are tokens on the board, at least one player can legally move, and therefore someone eventually wins.) Figure 2.4. Vera wins the 3 x 3 fake-sugar-packet game. for j PLACEQUEENS(Q[1..n),r): if r=n+1 print Q[1..n] else 1 to n legal TRUE for ir 1 to s 1 if (Q[i]=j) or (Q[i]=j+r-i) or (Q[i]=j-s+i) legal FALSE if legal Q[r]- j PLACEQUEENS(Q[1..n],r+1) (Recursion!>> Figure 2.2. Gauss and Laquire's backtracking algorithm for the n queens