Tous les états possibles d'un cube Rubik standard peuvent être résolus en 20 mouvements ou moins

Tous les états possibles d'un cube Rubik standard peuvent être résolus en 20 mouvements ou moins

Aujourd’hui, j’ai appris que les 43 252 003 274 489 856 000 positions d’un cube Rubik standard peuvent être résolues en 20 coups ou moins.

Toute personne qui souhaite sérieusement résoudre un cube Rubik utilise un algorithme ou une séquence d’étapes pour l’aider à résoudre le casse-tête. Il existe de nombreux algorithmes différents, dont la complexité et le nombre de mouvements requis varient, mais ceux qui peuvent être mémorisés et utilisés par un humain nécessitent généralement plus de quarante mouvements. Il s’avère cependant que ce nombre est un peu élevé, car il s’agit de la solution la plus efficace pour une position donnée sur un cube Rubik’s standard. Cela a été prouvé en juillet 2010 par Tomas Rokicki, Herbert Kociemba, Morley Davidson et John Dethridge, qui ont utilisé 35 «années CPU» * de temps de calcul, offertes par Google, pour prouver qu’il suffit d’un maximum de 20 déplacements à résoudre. n'importe quelle position sur un cube Rubik standard.

Fait intéressant, les chercheurs n’ont pas résolu chaque position par sa solution optimale. Au lieu de cela, une fois qu’ils ont découvert une position qui nécessitait définitivement 20 mouvements pour être résolu de la manière la plus efficace, ils n’ont pas essayé de résoudre les autres positions pour obtenir une solution optimale. Ils ont seulement exigé que le problème soit résolu en 20 coups ou moins, afin de s’assurer qu’il se trouvait en dessous de la limite supérieure maintenant connue. Tant que toutes les autres positions pourraient être résolues en deçà de ce montant, ils savaient que ce nombre devait être la limite supérieure des mouvements nécessaires pour résoudre toute position du cube Rubik’s standard. L’avantage de procéder de cette façon était qu’elle réduisait considérablement le nombre de calculs nécessaires pour prouver qu’aucune position sur le cube standard Rubik’s n’avait besoin de plus de 20 mouvements à résoudre.

* remarque: une «année CPU» correspond généralement au potentiel de travail pouvant être effectué par une machine Giga-FLOP en un an. Pour ceux qui ne sont pas familiers, un «FLOP» signifie simplement «Opérations en virgule flottante par seconde». Ainsi, une machine à un flop peut effectuer une opération par seconde. Une machine d'un Giga-FLOP, généralement abrégée en GFLOP, peut effectuer un milliard d'opérations par seconde. Pour prouver ce qui précède, les chercheurs ont utilisé 35 années CPU, soit environ 1 103 760 000 000 000 000 d’opérations, ce qui, vous le remarquerez, est inférieur au nombre de positions possibles du Rubik’s Cube. Pour en savoir plus sur la manière exacte dont ils ont réussi à réduire le problème de manière aussi radicale afin de pouvoir le faire en si peu d'opérations, cliquez ici.

Faits bonus:

  • Le Rubik’s Cube standard comprend 26 cubes avec des extensions internes qui s’emboîtent les unes dans les autres. Le cube central de chacun des six côtés est verrouillé au mécanisme central dans le cube, fournissant une structure de base pour les autres pièces.
  • Le moyen le plus simple de «résoudre» un cube Rubik’s est tout simplement de le démonter et de le réarranger de manière à ce qu’il soit résolu une fois remis en place. Déplacer les autocollants fonctionne aussi, mais risque de les déchirer et de rendre la tricherie évidente. 🙂
  • Le Rubik’s Cube a été inventé en 1974 par un professeur d’architecture hongrois, Ernő Rubik. À l'origine, il travaillait et attachait plusieurs blocs avec un élastique. Dans ce système original, après plusieurs rebondissements, l'élastique s'est rompu. Il s'est ensuite intéressé au problème structurel de la manière de déplacer les blocs indépendamment pour un nombre arbitraire de tours sans que le cube ne se désagrège. Fait intéressant, il n'avait pas réellement l'intention de créer un casse-tête lorsqu'il l'a conçu. Au contraire, il était plus intéressé par la résolution du problème structurel de la création du cube lui-même. Peu de temps après son invention, en 1975, il demanda et obtint le brevet hongrois HU170062, où son «cube magique» fut commercialisé pour la première fois.
  • Le puzzle a été vendu sous licence par Rubik à Ideal Toy Corp en 1980. Parce que Rubik n’avait pas satisfait aux conditions requises pour pouvoir déposer un brevet international dans les délais requis, il permettait à quiconque de fabriquer et de vendre l’un de ces cubes ”en dehors de la Hongrie. Pour aider à résoudre ce problème quelque peu, Ideal Toy Corp a changé le nom en «Rubik’s Cube», plus mémorable et marquable, plutôt que de conserver le nom générique de «Cube magique». Rubik lui-même a finalement obtenu des brevets pour le Rubik’s Cube dans divers pays, tels que les États-Unis en 1983.
  • Le Rubik's Cube a également été inventé de manière indépendante par un ingénieur autodidacte, Terutoshi Ishigi, au Japon en 1976. Son cube ressemblait presque au cube de Rubik à l'intérieur et à l'extérieur, bien qu'il n'en sût rien, puisqu'il avait Rubik. Rubik est cependant considéré comme l'inventeur, car Ishigi n'a pas reçu son brevet (au Japon) avant environ un an après celui de Rubik en Hongrie.
  • En janvier 2009, 350 millions de cubes avaient été vendus dans le monde.
  • Le Speedcubing consiste à essayer de résoudre un cube Rubik dans les plus brefs délais. Le premier championnat du monde organisé par le Livre Guinness des records du monde a eu lieu à Munich le 13 mars 1981.
  • Le record du monde actuel sur un cube Rubik’s 3 × 3 × 3 a été établi par Feliks Zemdegs, qui a réalisé son meilleur temps en 5.66 secondes au Melbourne Winter Open 2011.
  • Si vous exécutiez un tour du cube Rubik’s en une seconde, il vous faudrait 1 400 millions d’années pour passer en revue toutes les configurations de cube possibles.
  • En 1981, Mlle Schmit, de Düsseldorf, en Allemagne, a intenté une action en divorce contre son mari, citant le Rubik’s Cube comme co-intimé. Elle a déclaré: "Gunder ne me parle plus et quand il vient au lit, il est trop épuisé de jouer avec son cube pour me donner même un câlin."
  • Le Rubik's Cube le plus cher jamais fabriqué est le «Master Cube» créé par Diamond Cutters International en 1995. Ce cube de taille standard, entièrement fonctionnel, contient 22,5 carats d'améthyste, 34 carats de rubis et 34 carats d'émeraudes, le tout dans 18 carats. l'or et vaut environ 1,5 million de dollars.

Laissez Vos Commentaires