Skip to main content

Research Repository

See what's under the surface

Advanced Search

The algorithmics of solitaire-like games

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

Authors

Roland Backhouse roland.backhouse@nottingham.ac.uk

Wei Chen Wei Chen

João F. Ferreira João Ferreira



Abstract

One-person solitaire-like games are explored with a view to using them in teaching algorithmic problem solving. The key to understanding solutions to such games is the identification 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 polynomials 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.

Journal Article Type Article
Publication Date 2013-11
Journal Science of Computer Programming
Print ISSN 0167-6423
Electronic ISSN 0167-6423
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 78
Issue 11
Pages 2029-2046
APA6 Citation Backhouse, R., Chen, W., & Ferreira, J. F. (2013). The algorithmics of solitaire-like games. Science of Computer Programming, 78(11), 2029-2046. https://doi.org/10.1016/j.scico.2012.07.007
DOI https://doi.org/10.1016/j.scico.2012.07.007
Keywords Software
Publisher URL http://dx.doi.org/10.1016/j.scico.2012.07.007
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

SCP11Solitaire.pdf (275 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





Downloadable Citations

;