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.
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.
Original language | English |
---|---|
Title of host publication | Mathematics of Program Construction |
Subtitle of host publication | 10th International Conference, MPC 2010, Québec City, Canada, June 21-23, 2010. Proceedings |
Editors | Claude Bolduc, Jules Desharnais, Béchir Ktari |
Publisher | Springer |
Pages | 1-18 |
Number of pages | 18 |
Volume | 6120 |
ISBN (Electronic) | 978-3-642-13321-3 |
ISBN (Print) | 978-3-642-13320-6 |
DOIs | |
Publication status | Published - 2010 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin Heidelberg |
Volume | 6120 |
ISSN (Print) | 0302-9743 |
Keywords / Materials (for Non-textual outputs)
- Solitaire
- invariants
- tiling problems
- polynomials
- games on cyclotomic polynomials
- seven-trees-in-one
- nuclear pennies
- algorithm derivation