Morpion Solitaire - Enumeration

Michael Quist in 2008 (New-York 1974 - )

In March-April 2008, Michael Quist computed the numbers of distinct possible grids for the first moves, and for each game: 5D, 5T, 4D, 4T. Look also at his 3D/3T and finite 3D enumerations. Because he computed the 4D and 4T games up to the last possible grids, these games are now fully solved: look at the 4D and 4T record grids. Michael Quist, Ph.D., is a Research Scientist at Soar Technology, Michigan, USA.

In December 2011, Michael added the number of 5D distinct grids of 24 moves, also recomputing and confirming his enumeration of previous moves. His code is written in Java, and took around 5 days using a Macbook Pro (2.4GHz quad-core) at half capacity.

In the following table, all the numbers come from his computation, but for the 5T game the 20 first numbers were already known, and are confirmed by Michael. As mentioned by Jean-Charles Meyrignac at, they were first computed by:

The 5D, 5T, 4D, 4T enumerations are referenced respectively under the numbers A204107, A204108, A204109 and A204110 in the On-Line Encyclopedia of Integer Sequences, OEIS Foundation.

Graphics of numbers of distinct grids

Using the above numbers, here are graphics of the two fully enumerated games, 4D and 4T, really looking like bell curves, Gaussian functions:

If we now compare the common logarithms of 5D/5T/4D/4T enumerations, the 5D/5T curves (or more exactly their available beginning) show an inflexion point, not in 4D/4T curves:

The two first unknown numbers of distinct grids should be around 8e+11 (move number 24 at the 5D game) and 3e+12 (move number 23 at the 5T game).
The true number 8.32e+11 of move 24 at 5D, later computed in 2011 by Michael Quist, confirmed this estimate. Now the next unknown number, move 25 at 5D, should be around 3.9e+12.

© Christian Boyer,