João F. Ferreira (约恩)*

PhD Student on Algorithmic Problem Solving

[ CiteULike link ]
Authors

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

Downloads
  • Paper: PDF (the original publication will be made available at SpringerLink)
Status

To be published and presented at the Tenth International Conference on Mathematics of Program Construction (MPC'10) in June 2010. Roland Backhouse's invited talk will be based on this paper.

Abstract

Puzzles and games have been used for centuries to nurture problem-solving skills. Although often presented as isolated brain-teasers, the desire to know how to win makes games ideal examples for teaching algorithmic problem solving. With this in mind, this paper explores one-person solitaire-like games.

The key to understanding solutions to solitaire-like games is the identification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a collection of novel 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 inspired by earlier work by Chen and Backhouse on the relation between cyclotomic polynomials and generalisations of the seven-trees-in-one type isomorphism. We show how to derive algorithms to solve these games.

Keywords

Solitaire, invariants, tiling problems, polynomials, games on cyclotomic polynomials, seven-trees-in-one, nuclear pennies, algorithm derivation

Bibtex entry
@unpublished{jff*10:solitaire,
    title = {The Algorithmics of Solitaire-Like Games},
    author = {Backhouse, Roland and Chen, Wei and Ferreira, Jo\~{a}o F.},
    year = {2010},
    note = {To appear in the proceedings of MPC'10.},
    url = {http://joaoff.com/publications/2010/solitaire}
}
Related
History
  • 17 March 2010 — uploaded the paper