Le Rubik’s Cube peut être résolu en 20 coups ou moins

En utilisant 35 ans de temps CPU offert par Google, une équipe de chercheurs a trouvé que toutes les configurations possibles du Rubik’s Cube peuvent être résolues en 20 coups maximum. Personnellement, je sais faire une face parfaite.

Oui, chacune des 43.252.003.274.489.856.000 positions possibles du Rubik’s Cube peuvent être résolues en 20 coups ou moins.

Ce chiffre, le nombre de mouvement maximum pour résoudre le Cube en utilisant les algorithmes les plus efficaces possibles, s’appelle l’algorithme de Dieu. En 1981, on pensait que ce nombre était de 52. En 2005, c’était 28. Et aujourd’hui, en utilisant un programme qui peut résoudre le cube en 20 secondes, grâce à 35 années de CPU en veille donné par Google, il est prouvé que ce chiffre est de 20.

Bien sûr, pour ceux qui aiment le Cube, il y a plein de maths hyper-intéressantes derrière cette découverte. Pour nous, cela nous rappelle simplement que nous venons d’effectuer 400 mouvements de trop. [Cube 20 via Slashdot]

Crédit photo : M. Christian

Tags :
Dernières Questions sur UberGizmo Help
  1. @Pulco : «We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets»
    Donc 35 CPU sûr un an.

    C’est vrai que «grâce à 35 années de CPU en veille donné par Google» est un peu ambigüe.

  2. Wow c’est impressionant! J’en était resté à 28 moi.

    Je n’ai jamais compté le nombre de coup qu’il me faut pour le résoudre mais ça doit tourner autours de 100-150. Je le fais en une minute en moyenne :)

  3. Un pote à moi le fait en 15.81s avec une seule main ( c’est son record perso, et ce n’est pas des conneries).

    Perso je tourne aux alentour de 3min.. mais avec mes deux mains !

  4. @CrapaL: Le bon plan pour rendre dingue un « cubeur » ? Remonter les 20 pièces du cube pour atteindre une des configurations présentées ici :
    http://trucsmaths.free.fr/rubik.htm#impossible
    Il deviendra (à moins d’un nouveau démontage correctif) « insolutionnable ». Mélanger ensuite le cube pour dissimuler l’entourloupe… :)

    Petite précision (une coquille de traduction ?) : « Ce chiffre, le nombre de mouvement maximum pour résoudre le Cube en utilisant les algorithmes les plus efficaces possibles, s’appelle l’algorithme de Dieu. » Un algorithme n’est pas un nombre (!)… mais une suite d’opérations. Une bonne formulation pourrait être que « l’algorithme de Dieu constitue le « saint Graal » des « cubeurs » en cela qu’il fournit systématiquement la solution de résolution d’un cube la plus rapide, c’est à dire pour laquelle le nombre d’opérations nécessaires est minimal. » Bien entendu, on ne fera jamais qu’approcher cet algorithme idéal.

  5. Bof, trop nul, il dois me falloir un bon quart d’heure moi, et encore… Quand j’y arrive… Alors j’ose pas compter mes mouvements

  6. Ah ouais par contre:
    « Ce chiffre, le nombre de mouvement maximum pour résoudre le Cube  »

    43.252.003.274.489.856.000 est un nombre, pas un chiffre…

  7. Quelque chose me choque dans l’article…
    Si c’est le chiffre de Dieu, ils sont à coté de la plaque…
    Le chiffre de Dieu ne peut être que « 42 »…. 😛

  8. Pour ceux qui ne comprennent pas ce que veut dire 35 années CPU, il sagit d’un terme utilisé en projet informatique.

    Pour les projets, on parle généralement de jour-homme. Par exemple, je bosse actuellement sur un projet estimé à 1000 jour-homme, ce qui signifie que seul, j’en ai pour 1000 jours, a 10 =100 jours, a 100=10 jours. Cela permet au dirigeant de savoir combien de personnes il doit mettre sur le projet pour qu’il soit achevé à la date souhaité.

    35 ans CPU revient au même. 1 seul CPU = 35 ans de calcul…etc Le pret de Google ne signifie pas que X machines ont été monopolisées mais bien que leurs serveurs, lorsqu’ils étaient en veille, effectuaient une partie du calcul nécessaire. Avec des serveurs qui ont des dizaines de processeurs et des dizaines de serveurs en veille un peu partout dans le monde, 35 annés CPU sont rapidement atteintes…

  9. La Bible du Rubik’s Cube francophone : http://francocube.com/ ; ce site propose plusieurs méthodes (une méthode simple pour débuter, plusieurs méthodes de champions et une méthode intermédiaire) pour le Rubik’s Cube et tout un tas de puzzles du même genre.

    @Crapal, un rubik’s Cube est composé de 21 pièces : 12 arêtes, 8 coins et une pièce centrale à laquelle sont attachés les centres des 6 faces.

    @AP : un cube mal remonté, un cubeur s’en rend très bien compte à la résolution ; ça lui fera perdre moins de 10 secondes. Il est même possible de le voir sur un cube mélangé. On désigne pas algorithme de Dieu une méthode de résolution qui fait toujours le nombre minimal de coups et par nombre de Dieu la longueur de la solution la plus longue.

    @Difock788 : ces 35 années CPU ont pris une semaine à google ; tu as réussis quoi en 19 ans ? À prouver sue les 43 milliards de milliards de cas différents peuvent tous être résolus en moins de 20 coups ?

    @rommm & fake : les records mondiaux officiels : http://www.worldcubeassociation.org/results/regions.php
    et la page de Thibaut : http://www.worldcubeassociation.org/results/p.php?i=2006JACQ01

  10. Omg exelent le one handed rommm, je pensais que tu racontai des conneries en effet ^^ Mais j’ai reconnu les compet sur ta vidéo, jdonc forcément ca peut pas être un fake. Perso mon temps record à deux mains est de 42 secondes, sa me suffit mais sa dégoute de voir sa mdr.

  11. bonjour, peut-être ai-je lu l’article trop vite (en diagonale).
    Mais étant donné que les CPU n’ont pas les mêmes performances, n’aurait-il pas été utile de donner plus de détails (modèle de CPU, environnement, langage…) ?

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Publicité