Morpion Solitaire - NP-Hard Problem

Morpion Solitaire - NP-Hard Problem

Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman

Even if it is very easy to play Morpion Solitaire, it is proved that this game is NP-hard and the highest score is inapproximable, unless P=NP. A team of four persons, Erik D. Demaine, Martin L. Demaine (both from MIT, USA), Arthur Langerman (Langerman Diamonds, Belgium) and Stefan Langerman (University of Brussels, Belgium) proved this theorem in their "Morpion Solitaire" paper first published in 2004, and again in their improved version published in Theory of Computing Systems, 2006:

Theorem 2. For any k ≥ 3, it is NP-hard to find the longest play from a pattern of n dots, or even to find a play of length within n^1-ε of the longest play, for any constant ε > 0. This result holds for both variants of the game.

In their paper, k is the number of segments in a line (joining k+1 dots). And n is the number of dots in the initial pattern. Both variants are Touching and Disjoint. This means that the k and n values are, depending on the game:

Game		k	n
5	T	4	36
	D
4	T	3	24
	D

Their proof is correct for any general initial pattern, a Greek cross or not. Take care, however, we may know the best possible game in some particular cases: easy example, from an initial pattern of n = k aligned dots, the best score is only one move. Or for example from this pattern of 7 dots, we may get an infinite score. And we know now the best possible 4T and 4D games. For more details on what an NP-hard problem is, look at http://en.wikipedia.org/wiki/NP-hard or http://mathworld.wolfram.com/NP-HardProblem.html

The homepages of the four authors are:

George Bell, the author of an interesting website on Peg Solitaire, http://home.comcast.net/~gibell/pegsolitaire, sent me an amusing remark: the above paper is probably the only mathematical paper ever written by two pairs of father & son! But perhaps somebody knows of another example?

Erik D. Demaine, with Robert A. Hearn, in 2009 published the book "Games, Puzzles, and Computation" A. K. Peters Ltd, now part of CRC Press: http://www.crcpress.com/product/isbn/9781568813226. Morpion Solitaire is presented on page 180.