Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Arthur Langerman, and Stefan Langerman, “Morpion Solitaire”, in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 53–64.

BibTeX

@InProceedings{Morpion_FUN2004,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Arthur Langerman
                   and Stefan Langerman},
  TITLE         = {Morpion Solitaire},
  BOOKTITLE     = {Proceedings of the 3rd International Conference on Fun with
                   Algorithms (FUN 2004)},
  bookurl       = {http://www.di.unipi.it/fun04/},
  MONTH         = {May 26--28},
  YEAR          = 2004,
  ADDRESS       = {Isola d'Elba, Italy},
  PAGES         = {53--64},

  award         = {Invited to special issue of \emph{Theory of Computing Systems}.},
  papers        = {Morpion_TheoryComputSys},
  length        = {12 pages},
}

Abstract:

We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most general form, the game is NP-hard and the high score is inapproximable within n^1 − ε for any ε > 0 unless P = NP.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (335k), gzipped PostScript (80k), and PDF (208k).

See information on file formats.

[Google Scholar search]

Related papers:

Morpion_TheoryComputSys (Morpion Solitaire)