Paper by Martin L. Demaine

Reference:
Erik D. Demaine, Martin L. Demaine, Arthur Langerman, and Stefan Langerman, “Morpion Solitaire”, Theory of Computing Systems, volume 39, number 3, June 2006, pages 439–453. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.

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 n1 − ε for any ε > 0 unless P = NP.

Comments:
This paper is also available from SpringerLink.

Updates:
Christian Boyer maintains the latest Morpion results on morpionsolitaire.com. In particular, it is now known that G3(A3) = 35 and that G3(A3) = 62 (lower bounds in "New Heuristics for Morpion Solitaire" by Heikki Hyyrö and Timo Poranen, and upper bounds by enumeration by Michael Quist). There is also a new lower bound of G4(A4) ≥ 82 (by Tristan Cazenave), proposed upper bound of G4(A4) ≤ 138, and a new lower bound of G4(A4) ≥ 172 (by Christopher Rosin, beating the previous 34-year-old record by Charles-Henri Bruneau)

Copyright:
Copyright held by the authors.

Length:
The paper is 16 pages.

Availability:
The paper is available in PostScript (665k), gzipped PostScript (175k), and PDF (229k).
See information on file formats.
[Google Scholar search]

Related papers:
Morpion_FUN2004 (Morpion Solitaire)


See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 17, 2022 by Martin Demaine.