Algorithme pour toutes positions

[remiUP]

Bonjours,
je m'explique : j'aimerais savoir si il existerais un algorithme qui, répété des millions de fois, passerais par toutes les combinaisons totales d'un rubik's cube.
Cela m'aiderais beaucoup

merci d'avance

[TheDarkBlix]

Euh je ne crois pas, faut pas rêver non plus

[Philfully]

Il en existe un qui exécuté une seule fois passe par toutes les combinaisons, par contre

[SqAtx]

Ça s'appelle le Devil's algorithm, pour ceux qui seraient curieux

[Cubeur-manchot]

je m'explique : j'aimerais savoir si il existerais un algorithme qui, répété des millions de fois, passerais par toutes les combinaisons totales d'un rubik's cube.

Selon moi ça n'existe pas :
- Supposons par l'absurde que cet algorithme existe.
- Cet algorithme doit passer par toutes les combinaisons d'un rubik's cube. En particulier, exécuté un certain nombre de fois, il doit pouvoir résoudre n'importe quelle permutation des coins. On ne se servira que des coins (et même uniquement de leur orientation) pour démontrer qu'un tel algorithme n'existe pas (ce qui montrera aussi que ça n'existe pas même pour le 2x2x2 qui est plus simple, ainsi que pour toutes les tailles de rubik's cube "classiques").
- Donc n'importe quel coin doit pouvoir, après un certain nombre d'exécutions de l'algorithme, se retrouver à sa place normale, peu importe sa position initiale. Donc tout coin peut être envoyé à la place de chacun des autres coins du cube. Toute permutation d'un ensemble fini d'éléments dans lui-même (ici c'est une permutation des coins) s'écrivant comme produit de cycles, cela implique que la permutation des coins est un seul 8-cycle permutant les 8 coins.
- Lorsqu'on itère l'algorithme, cela revient à élever le cycle à une certaine puissance. Or lorsqu'on génère tous les cycles obtenus en élevant notre cycle initial à différentes puissances, on obtient uniquement 8 résultats différents (car 8 est la taille du cycle), ce sont les 8 cycles qu'on peut faire en faisant une "permutation circulaire" des éléments du cycle. Bref, on ne peut générer que 8 permutations différentes de coins. Or il existe 8! permutations différentes des coins (8 choix de placement pour le premier coin, 7 pour le deuxième, ...), c'est à dire 40320, ce qui est plus que ce qu'on peut générer.
- Cet algorithme ne peut pas résoudre toutes les permutations des coins uniquement en itérant un unique algorithme, donc à fortiori on ne peut pas résoudre toutes les combinaisons du rubik's cube uniquement en itérant ce seul algorithme.
- Donc il n'existe pas d'algorithme qui, itéré, résout toutes les combinaisons du rubik's cube. CQFD

La prépa me manque...

[TMOY]

Effectivement, un tel algo n'existe pas (et ceux qui parlent du devil's algorithm sont hors sujet).

Démo plus simple: s'il existait, le groupe serait cyclique, donc commutatif. Or il est facile de trouver deux éléments qui ne commutent pas.

[Cubeur-manchot]

Démo plus simple: s'il existait, le groupe serait cyclique, donc commutatif. Or il est facile de trouver deux éléments qui ne commutent pas.

J'avais oublié désolé C'est déjà tellement loin tout ça

[Cubezapiz]

Non, ça m'étonnerait beaucoup...

[Yoshi-San]

Non, ça m'étonnerait beaucoup...

Ahah, voilà de l'argumentation !
Plus sérieusement, je ne vois pas en quoi le Devil's algorithm est hors-sujet... remiUP demande une formule qui, répétée x fois, passe par toutes les combinaisons possibles du cube. Je ne connaissais pas cet algo, mais si il existe bel et bien alors OUI cette formule existe et c'est celle-ci tout simplement... enfin, il doit être tard et ça me semble trop simple. Il y a un truc qui doit m'échapper.
remiUP, si tu veux te renseigner sur cet algo, regarde ici ça parle en langage maths mais c'est compréhensible : http://anttila.ca/michael/devilsalgorithm/" onclick="window.open(this.href);return false; (ah oui, ça parle aussi en langage english ).

[Cubeur-manchot]

Je pense que les seules positions qu'on compte sont celles atteintes après exécution de l'algorithme un certain nombre de fois, mais pas les positions atteintes au milieu de la formule
Exemple : [R U2 R' U' R U' R']
Considérant cette formule, je ne peux atteindre que 6 positions différentes, celles définies par [R U2 R' U' R U' R'], [R U2 R' U' R U' R']2, [R U2 R' U' R U' R']3, etc.
La position atteinte par [R U2 R' U'] (par exemple) ne compte pas du coup.

je m'explique : j'aimerais savoir si il existerais un algorithme qui, répété des millions de fois, passerais par toutes les combinaisons totales d'un rubik's cube.

Bon ok c'est pas clairement explicité... mais c'est quand même presque sous-entendu

[pokekrom]

Ou un algo "méga" long ? Et on considère que le [R U2 R' U'] sur [R U2 R' U' R U' R'] est valable !

[JBM]

La question littérale: Algorithme pour toutes positions — existe-t-il un algorithme qui, répété des millions de fois, passerait par toutes les combinaisons totales d'un Rubik's cube?

Réécrite sans trop changer le sens: Existe-t-il un algorithme qui, répété un nombre suffisant de fois, passerait par toutes les états valides d'un Rubik's cube?

Réponse de TMOY (un peu hâtive selon moi, mais crédible): non.

Comment on peut comprendre l'esprit de la question avec un minimum de bonne foi: Existe-t-il une séquence de mouvements, de longueur indéterminée mais qui peut être arbitrairement longue, qui passe par tous les états valides d'un Rubik's cube?

Réponse: oui.

Donc oui, c'est ambigu, et ça l'est d'autant plus que le monde du cube fait un emploi assez osé du terme « algorithme ». Il faudrait que remiUP précise sa pensée, mais dans le doute, l'agorithme du diable n'est pas hors-sujet.

[Cubeur-manchot]

Effectivement, il nous faut les règles du jeu exprimées clairement, sinon tout le monde est d'accord

[JBM]

sinon tout le monde est d'accord

Et ça serait quand même dommage !

[Maitre Cube]

Sachant que l'on peut faire des 3 cycles de coins (c-a-d bouger 3 coins de manière cyclique, sans toucher au reste), on peut définir la position de 7 coins selon notre choix.
De même pour l'orientation, on peut orienter 2 coins séparéments.

Arrive alors le problème du dernier coin : on peut le bouger si l'on échange 2 arêtes. (genre PLL T,R,R', J ... et j'en passe)
On peut aussi faire des 3 cycles d'arêtes.

Je dirais donc (mais je suis pas matématiciens, mon truc c'est plus l'électronique / informatique) que Oui, il existe cet algo, mais NON on ne le connais pas encore.
On sait juste qu'il sera composé de plusieurs 3 cycles de coins, d'arêtes et d'e quelques deux cycle coin -> arête et par dessus des algos d'orientation d'arêtes et de coin.

Avec pas mal de set up, y'a moyen de faire un truc.

(un truc sale, mais faisable)

Mon avis n'est pas parole donnée, mais je pense que au moins mon raisonement est juste.

EDIT : c'est pour les positions valides...