Morpion solitaire is a one-player paper-and-pencil game. References to the game first appeared in French publications in the 1970s. In addition to being played recreationally, the game has been the subject of theoretical studies and computer searches for solutions.

Rules

The game is played on a square grid, assumed to be of unlimited size. The starting configuration has a set of 36 points marked on the grid in the form of a Greek cross. Each turn, the player makes a legal move by marking one additional point to create a new line of 5 marked points in a row. The line cannot overlap any previous line. The goal is to create as many new lines as possible before reaching a final configuration in which no further legal moves are available.

Variations

The rules may be varied by requiring lines of 4 marked points in a row rather than 5, with a reduced starting configuration. Also, the "disjoint" variation of the game does not allow two parallel lines to share an endpoint, whereas the standard "touching" version does allow this.

Records and computer searches

For the "touching" version of the game with lines consisting of 5 marked points, the present record of 172 lines was established on 2010 August 16, using a Monte-Carlo search by algorithmist Christopher Rosin. This is six moves more than the previous 1976 record of 170 lines. The 1976 record was done by hand, and computer searches have not been able to approach this record despite substantial progress, until August 2010 when Christopher Rosin used a Monte-Carlo search to obtain a result of 172 moves, exceeding the 1976 record.

For the "disjoint" version of the game with lines consisting of 5 marked points, the record of 80 lines has been obtained by computer search.

Theory

Generalized Morpion solitaire, in which the starting configuration may be any finite set of marked points, is a member of the NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

class of problems for which no efficient computational method for finding an optimal solution is known. Even the problem of finding an approximately optimal solution for generalized Morpion solitaire is NP-hard.

For the standard versions of Morpion solitaire, there do not exist infinitely large solutions; upper bounds have been proven. on the maximum number of lines that can be obtained.

External links

• Morpion Solitaire