Paper by Erik D. 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 Erik Demaine.
These pages are generated automagically from a
Last updated May 5, 2021 by