The Algorithmics of Solitaire-Like Games

Roland Backhouse, Wei Chen, JoãoF. Ferreira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationMathematics of Program Construction
Subtitle of host publication10th International Conference, MPC 2010, Québec City, Canada, June 21-23, 2010. Proceedings
EditorsClaude Bolduc, Jules Desharnais, Béchir Ktari
PublisherSpringer Berlin Heidelberg
Pages1-18
Number of pages18
Volume6120
ISBN (Electronic)978-3-642-13321-3
ISBN (Print)978-3-642-13320-6
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume6120
ISSN (Print)0302-9743

Keywords

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

Fingerprint

Dive into the research topics of 'The Algorithmics of Solitaire-Like Games'. Together they form a unique fingerprint.

Cite this