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 <euler@free.fr>
!
If you want to play to this game, there are several ways:
Other references:
http://lgimet.free.fr/JeuxStrat16.htm
http://www.recreomath.qc.ca/dict_solitaire_morpion.htm
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:
http://croix2malte.free.fr (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 |
