Starting with version 4 beta 15, a new feature has been added to Euler2000: the Morpion Solitaire Puzzle.

The aim of the game is pretty simple: with an initial board with 36 crosses, you have to trace new crosses -the more possible- respecting the following rules:
    - every new cross has to be aligned with 4 existing crosses
    - the alignments can be realised in every direction: horizontally, vertically or diagonally (45°)
    - no new alignment can contain 2 crosses (or more) already joined between themselves.

When 5 crosses are aligned, we trace a line between them.
When there is no move available, the game is finished, and the total number of crosses is the score of the board.

The current best PUBLISHED record of this game is 170.

However, in the journal Jeux & Stratégie number 18 and 19 dated from 1982-1983, three french men claimed they achieved records of 176, 179 and 233 crosses by presenting unverificable pictures of their end configuration.

If you reach a result above 160 crosses, please mail it to <> !

If you want to play to this game, there are several ways:

  1. Get an old version of Euler2000, which contains the game (it has been removed in the last version).
  2. (online Java applet with high scores)
  3. (Windows shareware version)
  4. (Windows shareware version)
  5. (a plugin for Zillion of Games)
  6. (a solving algorithm in CAML)
  7. (a Be version)
  8. (a Mac version with its Pascal source code)
  9. Play with a pencil and a paper !

Other references:
Hugues Juillé presented an algorithm playing this game in his P.h.d, reaching 122 lines (Pascal Zimmer later improved Hugues' algorithm and reached 143 lines).

15th April 2003: Thanks to Achim Flammenkamp's interest, I contacted both Charles-Henri Bruneau (holder of the first official 170 record) and Pierre Berloquin. Pierre Berloquin kindly sent me one record of 170 crosses dated 01/15/1982 by JB Bonté ! Achim Flammenkamp converted it to Denis Excoffier's format, and you can get the solution here. Excoffier's and JB Bonté's solutions are different, but VERY similar. You can get a screenshot from Excoffier's solution here and a screenshot from Bonté's solution here. Achim Flammenkamp suggested the following notation, in order to avoid duplicate solutions.

Each solution should be given in its standard form:
Its space and time normalized presentation is the standard form if coded as follows:
a solution is given/coded as the list of its moves in chronologic/play order lead in be a positive integer in ascii-decimal notation on the first line denoting the number of the following moves.
Each move should be coded as:
(x,y) z N *
moves should be separated by one new-line character (LF).
x and y are (non negative) integers in ascii-decimal representation
z is a single character chosen of the 4 elementic set { - , / , | , \ }
- denotes a corresponding line-alignment/cover with direction (1,0) [horiz]
/ denotes a corresponding line-alignment/cover with direction (1,-1)
| denotes a corresponding line-alignment/cover with direction (0,1) [vertic]
\ denotes a corresponding line-alignment/cover with direction (1,1)
N is one element of the set { -2, -1, 0, +1, +2 }
giving the center of the 5-point line segment relative to the cross position
* is an arbitrary typically empty string not containg a newline.
[reserved for further extensions]

E.g. in the old notation of Denis Excoffier
a single move might be presentated by:
(18,14) (16,12) (\)
The new form of the standard representation is then:
(18,14) \ -2
[explanation: \ means the direction (1,1). Multiply this by -2 and add it to (18,14) you get (16,12). Or visa verse: subtract (18,14) from (16,12)
resulting in (-2,-2) and divide this by the direction of (\) you get -2]
Interpretation: the N gives simply the amount of shift in direction z from (x,y) to get the center of the 5-point alignment of the cross.
Proposal: there may be anywhere any number of comment lines inserted, each starting with a # character as the very first. Because of application restrictions a line should contain at most 255 characters including the line delimiter (LF).

You can get the normalized solution in standard encoding here.
You can also get some statistics by Pascal Zimmer.
24th March 2003: Achim Flammenkamp improved his upper limit to the morpion solitaire: 324 crosses (362/4) ! He expects to reduce this bound to around 250-260 crosses. Here are the original Jeux&Stratégies articles (in French).

In Jeux&Stratégie number 17 page 96:
"Si l'on en juge par votre courrier la passion pour le morpion solitaire n'est plus à démontrer. Nous commençons à dépouiller les résultats de vos recherches et notamment ceux qui semblent mettre à mal les records dont nous avons fait mention dans notre article. Vous avez d'ailleurs été nombreux à nous signaler une erreur de numérotation dans la grille présentée page 29. Profitons-en pour signaler que nous avons « emprunté » ce document à une rubrique « Jeux & Paradoxes » de notre ami Pierre Berloquin dans Science& Vie. Bien mal acquis ne profite jamais ! Quoi qu'il en soit, cette erreur n'est finalement pas très grave puisqu'il semble bien que ce score soit largement battu. Après vérifications, attentives cette fois, nous publierons bien sûr les nouveaux records."

In Jeux&Stratégie number 18 page 101:
" La passion pour le morpion solitaire (voir J & S n° 16) ne se dément pas au fil des semaines et les 170 croix présentées comme le record semblent avoir été dépassées... Semblent bien ! Là est tout le problème. Il est horriblement difficile, voire impossible de retrouver l'ordre dans lequel les alignements ont été tracés et donc de vérifier si la grille proposée est ou non valable. En effet, vers le 30e coup, et parfois même avant, la pose d'une nouvelle croix offre 2, 3 ou 4 possibilités d'alignement: Lequel choisir ? Le nombre de possibilités s'accroît à mesure que le jeu avance. Tôt ou tard c'est l'impasse !
Aussi, nous prions les passionnés de morpion solitaire, et notamment ceux qui dépassent les 160 croix, de nous envoyer, en même temps que leur grille, la décomposition des coups réalisés. Nous nous adressons en premier chef à Sylvain Laurent et ses 233 croix ! à Jacques Erb (179 croix) et à Bruno Moret (176). Cette procédure permettra enfin de publier le hit-parade des morpionnistes, la grille record et quelques réflexions sur la finitude du morpion solitaire, qui semble désormais bien établie.
In english: several players broke the record previously established by Charles-Henri Bruneau (unpublished 170 crosses). The 3 best are Sylvain Laurent with 233 crosses, Jacques Erb with 179 crosses and Bruno Moret with 176 crosses. But these records are hard to verify, since it seems impossible to replay the games without a careful numerotation of their moves. So, the top players are asked to resubmit their solution with a decomposition of their moves, in order to publish a list of the best players, the record grid and some conclusions about the endness of this game. This was the last published article about this attracting game in Jeux&Stratégie.
20th March 2003: Achim Flammenkamp proved an upper limit to the morpion solitaire: 741 crosses !
1st February 2003: Pascal Zimmer explored the morpion solitaire upto 20 crosses, giving 22,663,033,612 positions (the computation took 100 hours) ! He estimates the total number of positions to 1023 !
13th January 2003:
Pascal Zimmer computer the number of positions upto 19 crosses !
23rd December 2002:
Pascal Zimmer found 90462493 positions with 16 crosses.
21st December 2002:
Hugues Juillé found a record of 122 with a genetic algorithm program. He sent me a link where you can play the game online: (beautiful Java Applet, but in french. Pascal Zimmer entered Denis Excoffier's solution). Vincent Everaert wrote a version of this game for Zillions of Games.
17th December 2002:
Pascal Zimmer indepently verified the number of positions upto 14 lines and found 36365073 positions with 15 lines (using his own program). He also noticed errors in the solution file from Denis Excoffier. Here is his fixed version. I also discovered an article about the problem.
21st November 2002:
Edward Brisse computed the number of positions with 13 lines : 10436597, and with 14 lines: 18107008.
2nd November 2002:
I finally fixed the bug that gave different values from Bainville's results and rewrote the code into assembly language. Edward Brisse was interested to continue the search, so all the results will now come from his computing efforts.
1st November 2002:
Using my own program on my old Celeron 450Mhz + 256Mb RAM, I'm currently computing the number of positions of the game. The number of positions differs from Eric Bainville's results, starting at 10th line, this may be a bug in my code.
Lines N (states) Growth TIME(s)
0 1   0
1 4 4 0
2 56 14 0
3 428 7.64 1
4 2741 6.40 1
5 13247 4.83 2
6 52059 3.93 7
7 167502 3.22 25
8 453377 2.71 76
9 1047750 2.31 212
10 2112634 2.02 500
11 3808004 1.80 1030
12 6369041 1.67 3393
13 10436597 1.64 15470
14 18107008 1.73 33187
15 36365073 2.01  
16 90462493 2.49  
17 282733629 3.13  
18 1074838721 3.80  
19 4716194782 4.39  
20 22663033612 4.80  

28th October 2002: You can get Denis Excoffier solution here.
12th September 2000:
Denis Excoffier sent me a solution with 170 crosses, congratulations ! I'll publish it when the program will be modified for a better gaming experience.
16th July 2000: Eric Bainville enumerated the starting positions upto move 12, here are his results:
Lines N (states) ln(N) TIME(s)
0 1 0 -
1 4 1.38 -
2 56 4.02 -
3 428 6.06 -
4 2741 7.91 3
5 13247 9.49 18
6 52059 10.86 97
7 167502 12.03 405
8 453377 13.02 1365
9 1047750 13.86 3823
10 2112634 14.56 9443
11 3808004 15.15 19950
12 6369041 15.66 41273

Go to the index page