L'algorithme de Dieu d'un casse tête est l'algorithme qui donne le nombre minimum de mouvements pour atteindre la solution, un être omniscient étant capable de déterminer le mouvement optimal à partir de n'importe quel état.
On défini également "le nombre de Dieu" comme étant le nombre d’opérations de l’algorithme de Dieu
Résumé
| Casse tête | Nombre de Dieu | Nb de combinaison |
| 2x2 | 11 | 3.6 x 106 |
| 3x3 | 20 | 4.3 x 1019 |
| Pyramorphix | 11 | 1.4 x 105 |
| Pyraminx | 15 | 7.5 x 107 |
| Square one | 13 | 5.5 x 1011 |
| Skewb | 11 | 3.1 x 106 |
| Skewb Diamond | 10 | 1.4 x 105 |
| Megaminx | >45 | 1.0 x 1068 |
Le 3x3x3
Trouver le nombre de Dieu du rubik's cube 3x3x3 a été l'objet de nombreuses études depuis les années 1980
Historique du "nombre de Dieu" du 3x3x3
| Date | Borne inf | Born sup | Ecart | Notes en Liens |
|---|---|---|---|---|
| July, 1981 | 18 | 52 | 34 | Morwen Thistlethwaite proves 52 moves suffice. |
| December, 1990 | 18 | 42 | 24 | Hans Kloosterman improves this to 42 moves. |
| May, 1992 | 18 | 39 | 21 | Michael Reid shows 39 moves is always sufficient. |
| May, 1992 | 18 | 37 | 19 | Dik Winter lowers this to 37 moves just one day later! |
| January, 1995 | 18 | 29 | 11 | Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm. |
| January, 1995 | 20 | 29 | 9 | Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves. |
| December, 2005 | 20 | 28 | 8 | Silviu Radu shows that 28 moves is always enough. |
| April, 2006 | 20 | 27 | 7 | Silviu Radu improves his bound to 27 moves. |
| May, 2007 | 20 | 26 | 6 | Dan Kunkle and Gene Cooperman prove 26 moves suffice. |
| March, 2008 | 20 | 25 | 5 | Tomas Rokicki cuts the upper bound to 25 moves. |
| April, 2008 | 20 | 23 | 3 | Tomas Rokicki and John Welborn reduce it to only 23 moves. |
| August, 2008 | 20 | 22 | 2 | Tomas Rokicki and John Welborn continue down to 22 moves. |
| July, 2010 | 20 | 20 | 0 | Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge prove that God's Number for the Cube is exactly 20. |
* En 1995, Michael Reid montre que ce nombre est au moins supérieur à 20, c’est à dire qu’il y a des positions qui ne peuvent pas être résolues en moins de 20 coups
La première position trouvé qui nécéssitait 20 coups a été appellé Superflip :
R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U
* En 2010, Une équipe est finalement parvenu à montrer que ce nombre de Dieu était en fait 20 en utilisant le procédé suivant (une démonstration détaillé est disponible Ici):
- Les 43 252 003 274 489 856 000 positions du cube ont été réparties en 2 217 093 120 ensembles de 19 508 428 800 configurations chacune. Ceci permet à chaque sous-problème de tenir dans la mémoire d’un PC moderne.
- Le nombre d’ensemble a été réduit à 55 882 296 en utilisant des symétries et ensembles couvrants.
- Les solutions recherchées n’étaient pas les optimales pour chaque position, mais celles de 20 mouvements ou moins — étant donné que la limite inférieure était déjà à 20 depuis 1995
- Un programme (code source) permet de résoudre chaque position (donc trouver le nombre de coup minimal) en 20 secondes environ.
- La résolution d'une configuration prenant environ 20 secondes, le calcul aurait duré 35 ans avec un PC normal, mais les nombreux ordinateurs fournis par Google ont permi d'effectuer le calcul en quelques semaines seulement.
au final :
- Le nombre de Dieu est 20 coups, si on ne prend pas en compte les doubles rotations
- pour une configuration de départ quelconque, il faut en moyenne 17.88 coups minimum pour résoudre le cube
- le nombre de combinaisons qui nécéssitent 20 coups représente 10-9% seulement du nombre de combinaisons total du Rubik's cube
Nombre de combinaisons correspondant au nombre de coup optimal
| Distance | Count of Positions |
|---|---|
| 0 | 1 |
| 1 | 18 |
| 2 | 243 |
| 3 | 3,240 |
| 4 | 43,239 |
| 5 | 574,908 |
| 6 | 7,618,438 |
| 7 | 100,803,036 |
| 8 | 1,332,343,288 |
| 9 | 17,596,479,795 |
| 10 | 232,248,063,316 |
| 11 | 3,063,288,809,012 |
| 12 | 40,374,425,656,248 |
| 13 | 531,653,418,284,628 |
| 14 | 6,989,320,578,825,358 |
| 15 | 91,365,146,187,124,313 |
| 16 | about 1,100,000,000,000,000,000 |
| 17 | about 12,000,000,000,000,000,000 |
| 18 | about 29,000,000,000,000,000,000 |
| 19 | about 1,500,000,000,000,000,000 |
| 20 | about 490,000,000 |
Le 2x2x2
Le 2x2x2 ayant seulement 3 674 160 combinaisons, il est très rapide de passer en revu toutes les combinaisons
on trouve donc que le nombre de Dieu pour le 2x2x2 est 11 ou 14 sans les demi-tours (quart de tour seulement)
Une démonstration détaillé est disponible ICI
Le Pyramorphix
le Pyramorphix a 136,080 positions différentes
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p | 1 | 6 | 27 | 120 | 534 | 2256 | 8633 | 26174 | 48585 | 39312 | 10260 | 172 |
On trouve un nombre de dieu de 11 coups
Le Pyraminx
De même que le 2x2x2, le pyraminx a seulement 75 582 720 combinaisons
si on enleve les rotations des coins sur eux-même, on obtient seulement 933,120 combinaisons
On trouve un nombre de dieu de 11 coups
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p | 1 | 8 | 48 | 288 | 1728 | 9896 | 51808 | 220111 | 480467 | 166276 | 2457 | 32 |
en rajoutant les 4 coups des 4 coins, on obtient un nombre de dieux de 15
Le Square one
le Square one a 552 738 816 000 positions différentes
| 1 | 64 |
|---|---|
| 2 | 1153 |
| 3 | 17050 |
| 4 | 235144 |
| 5 | 3091458 |
| 6 | 38893230 |
| 7 | 452031138 |
| 8 | 4459167504 |
| 9 | 33671064770 |
| 10 | 149502310936 |
| 11 | 183662070768 |
| 12 | 63945120032 |
| 13 | 157452752 |
On trouve un nombre de dieu de 13 coups
Le Skewb
le Skewb a 3 149 280 positions différentes
| 0 | 1 |
|---|---|
| 1 | 8 |
| 2 | 48 |
| 3 | 288 |
| 4 | 1,728 |
| 5 | 10,248 |
| 6 | 59,304 |
| 7 | 315,198 |
| 8 | 1,225,483 |
| 9 | 1,455,856 |
| 10 | 81,028 |
| 11 | 90 |
On trouve un nombre de dieu de 11 coups
Le Skewb Diamond
le Skewb Diamond a 138 240 positions différentes
| 0 | 1 |
|---|---|
| 1 | 8 |
| 2 | 48 |
| 3 | 288 |
| 4 | 1,632 |
| 5 | 8,568 |
| 6 | 36,114 |
| 7 | 74,799 |
| 8 | 16,547 |
| 9 | 220 |
| 10 | 15 |
On trouve un nombre de dieu de 10 coups
Le Megaminx
On rencontrait déjà des difficultés avec le 3x3 et ses 1019 combinaisons, alors on ne trouveras pas le nombre de dieu du megaminx avec ses 1063 combinaisons de suite.
Cependant on a montré que ce nombre était au moins 45 (source)
Les cubes NxNxN
après avoir trouvé le nombre de Dieu pour le 3x3, le nouveau défi pour les mathématiciens est de trouver celui des cubes NxN
soit UN le nombre de Dieu du cube NxNxN
on connait les 3 premiers termes de cette suite :
U1=1
U2=11
U3=20
UN= ?
Un groupe de chercheur a montré que pour tout N supérieur à 1,
UN=Θ(N2/log(N)) (preuve)
autrement dit
- il est existe m et M fixés tel que 0<m<M et le rapport entre UN et N2/log(N) est tourjours compris entre m et M
Conséquence :
On connait l'allure de la courbe qui donne le nombre de dieu en fonction du nombre de combinaison :
/fdata%2F4504915%2Favatar-blog-1237454290-tmpphp4nFvuw.jpeg){kind=avatar}