Paper by Martin L. Demaine

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.

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.

The paper is 12 pages.

The paper is available in PostScript (335k), gzipped PostScript (80k), and PDF (208k).
See information on file formats.
[Google Scholar search]

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