Port-and-sweep solitaire is a modern offshoot of the “peg solitaire” family of puzzles, where counters are removed from a board one at a time according to certain “jumping” rules. Peg Solitaire has an extensive mathematical literature which draws upon many subject areas, including abstract algebra, linear algebra, combinatorics, formal languages, and computational complexity. Many of the techniques should be adaptable to produce similar results for the analysis of port-and-sweep solitaire.
For this summer research project, a student will concentrate on solving at least one (or possibly more) of the following problems:
1. Resolve the one-dimensional “solitaire army” problem (i.e., the maximum distance that a counter can be advanced) for port-and-sweep solitaire. Some bounds are currently known, but the techniques that work for ordinary peg solitaire don’t quite suffice for port-and-sweep.
2. Prove that determining the solvability of arbitrary port-and-sweep solitaire positions is an NP-complete. It is likely that techniques from the article “Generalized Hi-Q is NP-Complete” can be adapted to this purpose.
3. Prove that the set of solvable port-and-sweep positions on specific boards (such as one-dimensional strips or 2xN rectangles) forms a regular language. It is likely that techniques from the article “One-Dimensional Peg Solitaire and Duotaire” can be adapted to this purpose.
4. Further develop the existing theory of invariants, resource counts and other mathematical tools to prove the impossibility of solving particular port-and-sweep problems.
5. Classify the boards of reasonable size on which one or more “complement” puzzles are solvable (these are puzzles where, in the course of the solution, exactly one token is removed from every square on the board).
I am also interested in developing algorithms to estimate the difficulty of particular port-and-sweep puzzles for human solvers, but this is an open-ended problem which doesn’t have a clear endpoint. We can discuss the feasibility of investigating this topic in parallel with one of the above, if the student finds it particularly interesting.
The project is to last six weeks, which should be enough time to obtain one or more results from the list above and prepare a first draft of an article suitable for submission to an appropriate journal such as Recreational Mathematics Magazine, Journal of Integer Sequences, Mathematics Magazine, or Involve.
Experience writing mathematical proofs is necessary.
Experience with TeX / LaTeX typesetting software will be helpful, but is not necessary.
Computer programming experience may be helpful, but is not necessary.
Successful completion (and ideally, enjoyment) of any of the following Gustavus courses would be ideal: 228 (Proofs), 265 (Theory of Computation), 256 (Discrete Calculus), 313 (Abstract Algebra), 375 (Algorithms). Students who have not had any of these classes are still welcome to apply, and describe their relevant experience and background.