23août/105

Lego Mindstorms et Rubik’s Cube

Ca y est j'ai craqué, j'ai acheté un Lego Mindstorms NXT !

Après avoir un peu fait joujou avec la bête, je me suis forcément attelé à la construction d'un robot permettant de résoudre un Rubik's Cube.

C'est une tâche bien plus ardue qu'il n'y paraît. En cherchant des conseils sur le net je suis tombé sur le site TiltedTwister. On y trouve les instructions de montage du robot très bien détaillées, ainsi que le problème de résolution.

Après une petite soirée de montage, voici donc ce que cela donne :

Lego Mindstorm + Rubik's Cube par piskocat

17août/100

Le nombre de Dieu enfin trouvé !

Cela fait des années que des mathématiciens, informaticiens cherchent en vain le nombre maximum de mouvements nécessaires pour résoudre un Rubik’s Cube à partir de n’importe qu’elle position.

Le challenge était de taille. Avec ses plus 43 milliards de milliards de possibilités un humain ne pourra jamais testé toutes les solutions possibles.

Il a donc fallu se pencher vers l’informatique. Oui mais l’ordinateur, aussi puissant soit-il est lui aussi limité.

Les chercheurs ont du regroupés l’ensemble des positions en 2.217.093.120 groupes de 19.508.428.800 positions chacun.

En supprimant les symétries le nombre de groupes a été réduits à 55.882.296.

L’algorithme qu’ils ont développé permet de trouver la solution minimale d’un cube en 20 secondes maximum.

A raison de 20 secondes par cube, il aurait fallu à leur ordinateur plus de 35 ans pour venir à bout des 55.882.296 groupes.
C’était sans compter Google, qui est venu prêter mains fortes, en offrant du temps de calcul. Grâce a cela le temps de calcul est tombé à quelques semaines.

Le nombre de mouvements maximum nécessaires pour résoudre un Rubik’s Cube à partir de n’importe qu’elle position est donc 20.

Les champions de Fewest moves ont encore de la marge !

   

Page optimized by WP Minify WordPress Plugin