João F. Ferreira

Roland Backhouse, Wei Chen and João F. Ferreira

• Paper: PDF (subject to editorial revisions)

Accepted for publication at Journal of Computer Programming.

One-person solitaire-like games are explored with a view to using them in teaching algo- rithmic problem solving. The key to understanding solutions to such games is the iden- tification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a novel class of one-person games.

The known classification of states of the game of (peg) solitaire into 16 equivalence classes is used to introduce the relevance of polynomial arithmetic. Then we give a novel algebraic formulation of the solution to a class of tiling problems. Finally, we introduce an infinite class of challenging one-person games, which we call “replacement-set games”, inspired by earlier work by Chen and Backhouse on the relation between cyclotomic poly- nomials and generalisations of the seven-trees-in-one type isomorphism. We present an algorithm to solve arbitrary instances of replacement-set games and we show various ways of constructing infinite (solvable) classes of replacement-set games.

Solitaire, tiling problems, cyclotomic polynomials, cyclotomic game, replacement-set game, seven-trees-in-one, algorithm derivation, invariants, type isomorphism

@article{jff*11:solitaire,
  author    = {Roland Carl Backhouse and
               Wei Chen and
               Jo{\~a}o F. Ferreira},
  title     = {The Algorithmics of Solitaire-Like Games},
  journal   = {Sci. Comput. Program.},
  volume    = {},
  number    = {},
  year      = {2011},
  pages     = {},
  url = {http://joaoff.com/publications/2011/solitaire-extended}
}

• From Seven-trees-in-one to Cyclotomics by Wei Chen and Roland Backhouse (2010)
• Conference version of this paper

• 18 September 2011 — uploaded the paper