Solitaire Clobber as an optimization problem on words
Vincent D. Blondel, Julien M. Hendrickx, Raphaël M. Jungers · Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) · 2008
We prove that the one-player game Solitaire clobber II is equivalent to an optimization problem on a set of words defined by seven classes of frobidden patterns when played on the line or on the cycle. This enables us to show that the game is solvable in linear time. Using this word representation, we also prove that, playing the a cycle it is always possible to remove at least 2n/3 pawns, and we give a configuration for which it is not possible to do better, answering questions recently raised by Duchêne et al.