Michael Quist en 2008 (New-York 1974 - )Morpion Solitaire - Enumération
Michael Quist en 2008 (New-York 1974 - )
En mars-avril 2008, Michael Quist a calculé les nombres de grilles distinctes possibles pour les premiers coups, et pour chaque jeu : 5D, 5T, 4D, 4T. Voir aussi ses énumérations 3D/3T et 3D fini. Puisqu'il a calculé les jeux 4D et 4T jusqu'aux denières grilles possibles, ces jeux sont maintenant complètement résolus : voir les grilles records 4D et 4T. Michael Quist, Ph.D., est Research Scientist à Soar Technology, Michigan, USA.
En décembre 2011, Michael a ajouté le nombre de grilles 5D distinctes de 24 coups, tout en recalculant et confirmant son énumération des coups précédents. Son code est écrit en Java, et a pris environ 5 jours en utilisant un Macbook Pro (2.4GHz quad-core) à mi-capacité.
Dans la table suivante, tous les nombres proviennent de ses calculs, mais au jeu 5T les 20 premiers nombres étaient déjà connus, et sont confirmés par Michael. Comme mentionné par Jean-Charles Meyrignac http://euler.free.fr/morpion.htm, ils ont été calculés initialement par :
Les énumérations 5D, 5T, 4D, 4T sont référencées respectivement sous les numéros A204107, A204108, A204109 et A204110 de la On-Line Encyclopedia of Integer Sequences, OEIS Foundation.
|
Coup |
5 |
4 |
||
|
D |
T |
D |
T |
|
|
1 |
4 |
4 |
5 |
5 |
|
2 |
55 |
56 |
106 |
107 |
|
3 |
404 |
428 |
1174 |
1212 |
|
4 |
2462 |
2741 |
10608 |
11307 |
|
5 |
11196 |
13247 |
73709 |
82008 |
|
6 |
41135 |
52059 |
419916 |
492459 |
|
7 |
122897 |
167502 |
1991917 |
2488802 |
|
8 |
307319 |
453377 |
8027941 |
10810906 |
|
9 |
652286 |
1047750 |
27842848 |
40954087 |
|
10 |
1199755 |
2112634 |
84184659 |
137334461 |
|
11 |
1950378 |
3808004 |
224072711 |
412834554 |
|
12 |
2885188 |
6369041 |
528129333 |
1123737371 |
|
13 |
4043706 |
10436597 |
1104419319 |
2789937671 |
|
14 |
5718245 |
18107008 |
2050193527 |
6354724457 |
|
15 |
8888485 |
36365073 |
3377728678 |
13348667549 |
|
16 |
16594082 |
90462493 |
4926536570 |
25978331545 |
|
17 |
39074532 |
282733629 |
6324442265 |
47005248571 |
|
18 |
115646521 |
1074838721 |
7094518159 |
79292133202 |
|
19 |
414852909 |
4716194782 |
6907808080 |
125052789966 |
|
20 |
1714717418 |
22663033612 |
5798009340 |
185063311252 |
|
21 |
7743579586 |
114269420056 |
4159280242 |
258100163444 |
|
22 |
36521752030 |
586835167740 |
2529867930 |
340693659166 |
|
23 |
174522348856 |
Inconnu ~ 3 x 10^12 |
1303170244 |
427231510805 |
|
24 |
832180499844 |
Inconnu ≠ 0 |
577789811 |
510573991860 |
|
25 |
Inconnu ~ 4 x 10^12 |
Inconnu ≠ 0 |
233092437 |
583199573552 |
|
26 |
Inconnu, mais ≠ 0 |
95176181 |
638498530949 |
|
|
27 |
42457190 |
671704764622 |
||
|
28 |
19421547 |
680361927366 |
||
|
29 |
7779370 |
664506187444 |
||
|
30 |
2318997 |
626592321191 |
||
|
31 |
441660 |
570974319683 |
||
|
32 |
65620 |
503018045238 |
||
|
33 |
10542 |
428268445219 |
||
|
34 |
1139 |
351981574359 |
||
|
35 |
278851125995 |
|||
|
36 |
0 |
212685481171 |
||
|
37 |
156060385490 |
|||
|
38 |
110147139843 |
|||
|
39 |
74812560627 |
|||
|
40 |
48944753049 |
|||
|
41 |
30875383909 |
|||
|
42 |
18784093173 |
|||
|
43 |
11004908127 |
|||
|
44 |
6187172765 |
|||
|
45 |
3322534859 |
|||
|
46 |
1697664286 |
|||
|
47 |
824285244 |
|||
|
48 |
380730137 |
|||
|
49 |
167670236 |
|||
|
50 |
70480255 |
|||
|
51 |
28308310 |
|||
|
52 |
10909843 |
|||
|
53 |
4040927 |
|||
|
54 |
1427437 |
|||
|
55 |
466917 |
|||
|
56 |
132561 |
|||
|
57 |
31740 |
|||
|
58 |
7045 |
|||
|
59 |
1573 |
|||
|
60 |
405 |
|||
|
61 |
108 |
|||
|
62 |
||||
|
63 |
0 |
|||
Graphiques des nombres de grilles distinctes
En utilisant les nombres ci-dessus, voilà les graphiques des deux jeux complètement énumérés, 4D et 4T, qui ressemblent fort à des courbes de Gauss :
Si l'on compare maintenant les logarithmes décimaux des énumérations 5D/5T/4D/4T, les courbes 5D/5T (ou plus exactement leur début disponible) montrent un point d'inflexion, absent des courbes 4D/4T :
Les deux premiers nombres inconnus de grilles
distinctes devraient être autour de 8e+11 (coup numéro 24
au jeu 5D) et 3e+12 (coup numéro 23 au jeu 5T).
Le
nombre réel 8.32e+11 de coup 24 au 5D, ensuite caclulé
en 2011 par Michael Quist, a confirmé cette estimation. Maintenant
le nombre inconnu suivant, coup 25 au 5D, devrait être autour de 3.9e+12.
© Christian Boyer, www.morpionsolitaire.com