Peg Solitaire is a game consisting of a playing board with $33$ holes together with $32$ pegs. In the picture above, the hole in the center is empty and the remaining holes contain pegs. The goal is to remove all the pieces except one, which should be in the center. A piece can be removed by jumping an adjacent piece over it into an empty hole. Jumps are permitted horizontally or vertically, but not diagonally.

Your assignment consists of two parts, plus one extra credit part:

Explain $($in words$)$ why Breadth First Search and Iterative Deepening are not good methods for this problem.

Program Depth First Search on this problem. You must create classes for the playing board, the successor function and the goal test, and make your classes work with the search code from the text.

Design an admissible A$*$ heuristic for this problem and test its effectiveness.