Consider the problem of solving two 8-puzzles.





a. Give a complete problem formulation.




b. How large is the reachable state space? Give an exact numerical expression.




c. Suppose we make the problem adversarial as follows: the two players take turns moving; a coin is flipped to determine the puzzle on which to make a move in that turn; and the winner is the first to solve one puzzle. Which algorithm can be used to choose a move in this setting?




d. Give an informal proof that someone will eventually win if both play perfectly.