First solve the problems that are given. Next, make a list of the subproblems you considered while solving them. Discuss how a computer might be programmed to solve each of the given problems, and how each of the problems might be represented to the computer. If you find a state-space representation for a problem, estimate the size of the state space and try to identify heuristics and algorithms the machine could use to search it. If computer time is available to you, choose a problem and try to implement a computer program that can solve it.

A board contains 33 standard-size holes in which have been placed 32 standard-size, removable pegs. The goal is to remove the pegs in such a way that a board is obtained which contains only one peg, placed in the (initially empty) center hole. Pegs may be removed only by "jumping" them, as in checkers; that is, a peg A may be removed if and only if there is a peg B next (left, up, right, or down) to it and an empty hole C on the opposite side, and the removal of peg A is accompanied by the placing of peg B in hole C.