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.

BibTeX

@Article{Morpion_TheoryComputSys,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Arthur Langerman
                   and Stefan Langerman},
  TITLE         = {Morpion Solitaire},
  JOURNAL       = {Theory of Computing Systems},
  journalurl    = {https://link.springer.com/journal/224},
  VOLUME        = 39,
  NUMBER        = 3,
  MONTH         = {June},
  YEAR          = 2006,
  PAGES         = {439--453},
  NOTE          = {Special issue of selected papers from the 3rd International
                   Conference on Fun with Algorithms, 2004.},

  updates       = {Christian Boyer maintains the latest Morpion results on
                   <A HREF="http://www.morpionsolitaire.com/">morpionsolitaire.com</A>.
                   In particular, it is now known that
                   <I>G</I><SUB>3</SUB>(<I>A</I><SUB>3</SUB>)&nbsp;=&nbsp;35
                   and that
                   <I>G</I>&prime;<SUB>3</SUB>(<I>A</I><SUB>3</SUB>)&nbsp;=&nbsp;62
                   (lower bounds in "<A HREF="http://www.cs.uta.fi/~tp/pub/morpion-article.pdf">New Heuristics for Morpion Solitaire</A>"
                   by Heikki Hyyr&ouml; and Timo Poranen,
                   and upper bounds by <A HREF="http://www.morpionsolitaire.com/English/Enumeration.htm">enumeration</A>
                   by Michael Quist).
                   There is also a new lower bound of
                   <I>G</I><SUB>4</SUB>(<I>A</I><SUB>4</SUB>)&nbsp;&ge;&nbsp;82 (by Tristan Cazenave),
                   proposed upper bound of
                   <I>G</I><SUB>4</SUB>(<I>A</I><SUB>4</SUB>)&nbsp;&le;&nbsp;138, and
                   a new lower bound of
                   <I>G</I>&prime;<SUB>4</SUB>(<I>A</I><SUB>4</SUB>)&nbsp;&ge;&nbsp;172 (by Christopher Rosin, beating the previous 34-year-old record by Charles-Henri Bruneau)},
  award         = {Translated into Portuguese: ``Cinco-em-linha solit\'ario'',
                   \emph{Boletim da Sociedade Portuguesa de Matem\'atica}
                   54:125--142, May 2006.},
  length        = {16 pages},
  papers        = {Morpion_FUN2004},
  replaces      = {Morpion_FUN2004},
  copyright     = {Copyright held by the authors.},
  doi           = {https://dx.doi.org/10.1007/s00224-005-1240-4},
  dblp          = {https://dblp.org/rec/journals/mst/DemaineDLL06},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/s00224-005-1240-4">SpringerLink</A>.},
}

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)