How Hard Is Peg Solitaire?
Most people have a hard time solving the Triangle(5) board by hand, and Triangle(6) is more difficult. Let us consider the complement problem on an arbitrarily large (null-class) triangular board. We just want to find any solution to this problem, not the shortest solution like you see in the solution catalogs. Intuitively, it seems obvious that the larger the board, the harder this must be to solve. This seems to be confirmed by exhaustive computer search calculations. Many people (including myself) have written programs that try to find a solution by going through all possible jump sequences, or all possible board states that can be reached. If you apply such programs to larger and larger boards, the time to find a solution increases exponentially, until at some point, your program will not be able to find a solution after running many hours. However, I have been able to show that far from being obvious, the intuition above is actually incorrect, and that the complement problem does
