The game of solitaire is well known: already played in Roman times, it spread in France starting in the 16th century and is still sold today. While the usual boards are cross-shaped, this article will confine itself to the one-dimensional version of the game, on a board of n cells numbered from 0 to n ‒ 1.
On each turn, a peg, as in checkers, can capture one of its neighbors if the next cell is empty. Here is an example of a capture in which peg 4 captures peg 3, moving to cell 2.
At the start, the board is completely full, and you may remove any peg you choose to begin play. You must then chain captures together to finish with a single peg on the board. Is it possible to win? If so, how?
Let's start by looking at small values of n. For n = 3, you can win by removing the peg at one of the ends, whereas removing the center peg leaves you stuck.
