The algorithmics of solitaire-like games
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, tilin...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2012
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/1854/ |
| _version_ | 1848790675041026048 |
|---|---|
| author | Backhouse, Roland Chen, Wei Ferreira, João F. |
| author_facet | Backhouse, Roland Chen, Wei Ferreira, João F. |
| author_sort | Backhouse, Roland |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:16:23Z |
| format | Article |
| id | nottingham-1854 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:16:23Z |
| publishDate | 2012 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-18542020-05-04T20:21:30Z https://eprints.nottingham.ac.uk/1854/ The algorithmics of solitaire-like games Backhouse, Roland Chen, Wei Ferreira, João F. 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. Elsevier 2012-07 Article NonPeerReviewed Backhouse, Roland, Chen, Wei and Ferreira, João F. (2012) The algorithmics of solitaire-like games. Science of Computer Programming . ISSN 0167-6423 (In Press) Solitaire tiling problems cyclotomic polynomial cyclotomic game replacement-set game seven-trees-in-one algorithm derivation invariants type isomorphism http://dx.doi.org/10.1016/j.scico.2012.07.007 10.1016/j.scico.2012.07.007 10.1016/j.scico.2012.07.007 10.1016/j.scico.2012.07.007 |
| spellingShingle | Solitaire tiling problems cyclotomic polynomial cyclotomic game replacement-set game seven-trees-in-one algorithm derivation invariants type isomorphism Backhouse, Roland Chen, Wei Ferreira, João F. The algorithmics of solitaire-like games |
| title | The algorithmics of solitaire-like games |
| title_full | The algorithmics of solitaire-like games |
| title_fullStr | The algorithmics of solitaire-like games |
| title_full_unstemmed | The algorithmics of solitaire-like games |
| title_short | The algorithmics of solitaire-like games |
| title_sort | algorithmics of solitaire-like games |
| topic | Solitaire tiling problems cyclotomic polynomial cyclotomic game replacement-set game seven-trees-in-one algorithm derivation invariants type isomorphism |
| url | https://eprints.nottingham.ac.uk/1854/ https://eprints.nottingham.ac.uk/1854/ https://eprints.nottingham.ac.uk/1854/ |