Algorithme pour toutes positions

[JBM]

Si on n'en est qu'à prouver qu'on peut passer par tous les états valides, ce n'est pas la peine de s'embêter à les caractériser (permutations/orientations/parités, ou tout autre système finalement): il suffit d'accepter que le nombre d'états est fini, qu'on sait tous les résoudre, qu'on peut donc tous les atteindre par une résolution inversée.

C'est quand on cherche à mettre des contraintes plus fortes que ça devient difficile. Exemple 1: que le chemin suivi soit de la forme Aⁿ où A est une séquence de mouvements fixe quelconque, et que tous les états soient atteints entre ces A → pas facile. Exemple 2: que le chemin soit minimal en QTM → ça a été résolu il y a trois ans.

[Cubeur-manchot]

Exemple 1: que le chemin suivi soit de la forme Aⁿ où A est une séquence de mouvements fixe quelconque, et que tous les états soient atteints entre ces A → pas facile

Bah justement, pas possible !

Exemple 2: que le chemin soit minimal en QTM → ça a été résolu il y a trois ans.

J'ai une toute petite question à propos de ça : l'algorithme dont il parle c'est bien un Devil's Algorithm, un algorithme qui passe par toutes les combinaisons du rubik's cube, mais qui soit en plus optimal en nombre de mouvements ? Il me semblait que justement, le problème était en recherche, ça m'étonne...

[pokekrom]

Ou décomposer en deux ou trois algo, un pour les coins et un pour les arrêtes (à voir pour les centres) ce serait un algo du diablotin et non du diable ^^

[JBM]

Exemple 1: que le chemin suivi soit de la forme Aⁿ où A est une séquence de mouvements fixe quelconque, et que tous les états soient atteints entre ces A → pas facile

Bah justement, pas possible !

Je ne dis pas le contraire, mais dans l'état actuel du fil je concevrais qu'un extérieur ait le doute.

Exemple 2: que le chemin soit minimal en QTM → ça a été résolu il y a trois ans.

J'ai une toute petite question à propos de ça : l'algorithme dont il parle c'est bien un Devil's Algorithm, un algorithme qui passe par toutes les combinaisons du rubik's cube, mais qui soit en plus optimal en nombre de mouvements ? Il me semblait que justement, le problème était en recherche, ça m'étonne...

C'est sûr, il l'a été, mais de tout le fil de speedsolving.com, personne n'a réfuté depuis, donc en attendant de vérifier moi-même (ha!), je vais présumer le résultat valide.

[Gothmog]

On peut voir le problème différemment.
Existe-t-il un algorithme qui répété suffisamment de fois passe par toutes les combinaisons ?
La réponse pour moi est oui et le nombre suffisant de fois est un.

Démonstration
On numérote Ci pour i de 1 à 43252003274489856000 toutes les combinaisons du cube.
Ensuite, on trouve une suite de mouvements qui va de C1 à C2,
on concatène une suite de mouvements qui va de C2 à C3,
on concatène une suite de mouvements qui va de de C3 à C4,
et ainsi de suite jusqu'à avoir épuisé toutes les combinaisons.
On obtient ainsi un algorithme qui passe par toutes les combinaisons.

Evidemment, c'est un peu de la triche puisque c'est impossible (à mon humble avis) à réaliser en pratique.
Ce n'est pas non plus l'esprit de la question.
De plus, cet algorithme contient au moins autant de mouvements qu'il y a de positions du cube et sans doute beaucoup plus.
On pourrait se demander si le graphe des états du cube vis-à-vis des 6 générateurs classiques est hamiltonien.
On pourrait aussi essayer de trouver une courte séquence et travailler sur les classes (à gauche ou à droite, je ne sais jamais) du sous-groupe engendré.
L'idée serait de compresser l'écriture de cet algorithme mais je pense que ça reste encore complètement dingue à écrire.

Le seul espoir serait d'imbriquer des sous-groupes (un peu comme les premiers pas vers le God's number) pour construire quelque chose de faisable (avec un ordi à tout le moins).
Mais bon, même en passant par un état du cube par cycle d'horloge d'un PC moderne, faire tourner la chose jusqu'au bout prendrait encore des siècles.

[JBM]

On pourrait se demander si le graphe des états du cube vis-à-vis des 6 générateurs classiques est hamiltonien.

Il l'est, et tu le saurais si tu avais lu le fil avant de poster

[Cubeur-manchot]

Evidemment, c'est un peu de la triche puisque c'est impossible (à mon humble avis) à réaliser en pratique.

J'ai fait un petit calcul vite fait, et si tu veux passer par toutes les combinaisons uniquement avec tes petites mimines et un rubik's cube classique, et si tu comptes y arriver en un siècle, l'énergie cinétique de rotation qu'aurait le cube serait de l'ordre de l'énergie de l'explosion nucléaire d'Hiroshima (précision : le cube aurait cette énergie cinétique pendant 100 ans...).
Bref, fais gaffe quand même...

Le seul espoir serait d'imbriquer des sous-groupes

D'après ce que j'ai compris, c'est comme ça que le type (celui qui a montré que le graphe du cube était Hamiltonien) a fait : il a trouvé un chemin dans le groupe généré par <R,U>, puis il l'a étendu en rajoutant successivement les mouvements L, D et F (pas de mouvement B, ce n'est pas un oubli)

L'idée serait de compresser l'écriture de cet algorithme mais je pense que ça reste encore complètement dingue à écrire.

Ouais, on tape dans les très grands nombres, crois-moi !

en attendant de vérifier moi-même (ha!), je vais présumer le résultat valide.

Si tu veux tester ça avec un bon PC, il te faudrait environ quelques fois l'âge de l'univers

[JBM]

en attendant de vérifier moi-même (ha!), je vais présumer le résultat valide.

Si tu veux tester ça avec un bon PC, il te faudrait environ quelques fois l'âge de l'univers

Non non, au crayon et au papier, comme toutes les bonnes solutions à la Project Euler ! Avec tolérance pour une assistance informatique sporadique.
Mon « ha ! » ne signifiait pas que je comptais faire une vérification pas à pas de l'exhaustivité du parcours et que j'en doutais du bien-fondé de la démarche, simplement que malgré mes allégations je n'arriverai probablement plus jamais à dégager dans ma vie suffisamment de temps pour mener à bien une analyse sensée. À mon grand dam.

[Cubeur-manchot]

Je ne connais pas tes capacités Mais les démonstrations papier-crayon sont plus courtes que celles par recherche exhaustive tout est question de volonté

[Athalis]

Bon, après avoir lu toute la conversation, je commence a avoir mal à la tête, c'est normal?

[Cubeur-manchot]

Si tu n'es pas habitué à ce genre de conversations et que ton cerveau n'a pas explosé, ce n'est pas normal Moi j'adore

[Athalis]

bon je vais donc me retirer, et essayez de mettre une balise "TOPIC DANGEREUX" sur le sujet pour ne pas décimer la communauté francocube! XD

[Cubeur-manchot]

Au pire quelques neurones seront grillés, mais rien de trop grave