Paper by Erik D. 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 n^1 − ε 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 G₃(A₃) = 35 and that G′₃(A₃) = 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 G₄(A₄) ≥ 82 (by Tristan Cazenave), proposed upper bound of G₄(A₄) ≤ 138, and a new lower bound of G′₄(A₄) ≥ 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)