Le Cube de Rubik en traduction 20 se déplace

Toute position du cube de Rubik peut être résolu en moins de 20 étapes.

Il ya quelques années, il a été prouvé que, pour Cube de Rubik est la solution pour 23 se déplace. Maintenant, le nombre est tombé à 20. Pour ce faire, vous avez besoin de 35 (trente-cinq) ans de temps d’ordinateur offert par Google.

Chaque bloc de la décision d’utiliser son propre algorithme — une séquence d’étapes pour réaliser la configuration souhaitée. Par exemple, un algorithme est destiné à résoudre la face supérieure et les autres — moyennes de positionnement bords. Il existe de nombreux algorithmes différents, variant en complexité et le nombre d’étapes nécessaires, mais ceux qui se souviennent de personnes nécessitent généralement plus de 40 étapes.

Il est raisonnable de supposer que Dieu peut utiliser un algorithme plus efficace qui résout le problème de la meilleure certain nombre de mesures. Cet algorithme est connu comme «l’algorithme de Dieu». Le nombre d’étapes dans le pire des cas, a appelé le numéro de Dieu.

En fin de compte, il a été montré que ce nombre — 20.

Après l’invention de cube de Rubik a fallu quinze ans pour trouver une position qui est certainement résolu en 20 étapes. Après 15 ans, nous allons prouver que 20 coups suffisent pour toute position.

Histoire de Dieu

En 1980, il a été constaté que la limite inférieure — 18, et le sommet — probablement autour de 80. Dans le tableau résume l’ensemble des résultats:

nous l’avons fait

Comme nous avons traité 43 252 003 274 489 856 000 positions Cube de Rubik?

  • Nous avons partagé toutes les positions sur les ensembles de 2217093120 à 19508428800 à chaque position.
  • Nous avons réduit le nombre d’ensembles de solutions sur la base de symétrie 55888296 et le couvercle ensemble.
  • Nous ne cherchons pas la meilleure solution et la seule solution à la longueur de 20 ou moins d’étapes.
  • Nous avons écrit un programme qui trouve la solution à un ensemble pendant 20 secondes.
  • Il a fallu 35 ans de temps d’ordinateur pour trouver des solutions à toutes les configurations dans chacune des 55.888.296 ensembles.

Nous avons partagé une grande tâche en plus petits sous-tâches 2217093120: chaque consistait 19508428800 positions différentes. Un tel sous-tâche intégrer facilement dans la mémoire de l’ordinateur moderne, et cette méthode va rapidement trouver une solution.

Si vous retournez le Cube de Rubik gauche et à droite ou de haut en bas, puis, en fait, rien ne va changer: le nombre d’étapes dans la décision restera le même. Au lieu d’avoir à faire face à tous ces éléments, vous pouvez obtenir une solution pour l’un et l’étendre à la position de retour. Il ya 24 orientations différentes dans l’espace et 2 reflètent les dispositions de dés pour chaque poste, ce qui réduit le nombre d’éléments résolus 48 fois. Si nous utilisons le même raisonnement et utilisons la recherche tâche «ensemble de couverture», puis le nombre de sous-tâches est réduite de 2217093120 à 55.882.296.

La solution contient un nombre suffisant d’étapes, mais pas plus que nécessaire. Comme il est déjà connu pour une position, ce qui nécessite 20 étapes, nous ne pouvons pas trouver une solution optimale pour chaque position, et la seule solution en 20 coups ou moins. Ce accélère grandement la tâche.

Équipement

Nous étions en mesure de résoudre les sous-tâches 55882296 dans les installations de Google et d’effectuer tous les calculs dans quelques semaines. Google ne divulgue pas les caractéristiques des ordinateurs, mais il a été dépensé 1,1 milliards secondes de temps d’ordinateur (Intel Nehalem, à quatre cœurs, 2,8 GHz) pour effectuer des calculs.

Le plus dur poziitsiya

Nous avons connu pendant 15 ans, il ya un poste qui exige 20 étapes, mais nous avons prouvé que pour l’une des positions et pas plus.

solutions d’articles en 20 étapes sont rares, mais il est possible de rencontrer dans la réalité. La probabilité de trouver cette position varie entre 10 (-9) et 10 (-8). Nous ne connaissons pas le nombre exact de ces positions.

Le tableau donne une estimation du nombre de postes pour chaque décision de longueur.

Pour des longueurs de 16 ou plus, les nombres sont exemplaires. Notre recherche a confirmé toutes les entrées et y compris 14 lignes et 15 lignes — un nouveau résultat. Le 11 Août, nous avons trouvé 12 millions d’articles d’une longueur de solutions 20. La position était difficile pour nos programmes:

Share →