Spiked Math: MPF - Morpion Solitaire

Greg Bernhardt

You can try the game out in Java by visiting the following links (using the 5T setting, if applicable):

• (Written by Daniel Tomasiewicz): http://fourstaples.com/morpion

Try the game out on your own and see if you can last for more than 178 moves or even 200 moves! Otherwise, here are some references and hints:

• More information about Morpion Solitaire: http://www.morpionsolitaire.com/
• Paper by Erik Demaine, Martin Demaine, Arthur Langerman and Stefan Langerman that proves in its most general form that the game is NP-hard and the highest score is inapproximable, unless P=NP: http://erikdemaine.org/papers/Morpion_FUN2004/paper.pdf
• Wikipedia entry on the game: http://en.wikipedia.org/wiki/Morpion_solitaire
• Note that if you can get MORE than 178 moves, then you will hold the new WORLD RECORD! (assuming the information on that website is accurate and up-to-date).

More...

Borek

While a kid I spend many classes playing a variant of the solitaire - we started with the same cross, but if I remember correctly we were adding just a fourth point to create a 4 point line and the task was to fill whole interior with crossed squares (that is, each square inside the cross has to have all four sides and both diagonals.