Paper by Martin L. 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.

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]