introduction

Je suis Nyanyan, un ingénieur matériel / logiciel qui aime la concurrence des cubes de vitesse, qui résout rapidement les cubes rubic. Cette fois, j'expliquerai Problème de Floppy Cube de PC Koshien 2014, et de là, Rubik Cube etc. J'expliquerai la ** méthode d'écriture à usage général ** du programme qui résout le puzzle en trois dimensions.

Je fais actuellement un robot qui (probablement) le plus rapide pour résoudre un cube rubic 2x2x2, et j'ai utilisé les connaissances que j'avais cultivées là-bas pour résoudre ce problème. Cette connaissance est exagérée pour ce problème, mais j'écris cet article parce que je serais ravi de le présenter.

Aperçu du problème

Qu'est-ce qu'un cube de disquette?

Image from iOS(10).jpg C'est un puzzle comme l'image. On l'appelle parfois "Rubik Cube avec une seule étape", et c'est vrai. Le fait est qu'il existe quatre axes (haut, bas, gauche et droite) qui peuvent être alignés en les faisant pivoter de 180 degrés. Selon la version anglaise du wiki, le nombre de combinaisons est de 192 $ $ (ce qui est assez élevé étant donné qu'un cube Rubik normal vaut 4,3 $ \ times10 ^ {19} $. Le nombre de Dieu (jusqu'à $ N $, que vous pouvez toujours obtenir si vous avez une main) est de 8 $.

problème

Le texte intégral de la question est ici L'état de couleur de chaque côté du cube de disquette est donné sous forme de liste de nombres, veuillez donc indiquer le nombre de mains que vous pouvez aligner à partir de cet état. Avec une limite de mémoire de 131072 $ KB et une limite de temps de $ 1 $ secondes, vous recevrez jusqu'à 30 états de puzzle (c'est-à-dire que vous devez produire des réponses dans un délai moyen de 33 $ ms par puzzle).

L'état du puzzle est donné par une liste de nombres. Cette séquence est le nombre d'autocollants de puzzle (zones colorées) 30 $ (9 $ au recto et au verso $ \ fois 2 = 18 $, 3 $ sur les côtés $ \ times4 = 12 $ pour un total de 30 $ $ ), Chaque couleur est représentée par le nombre $ 1,2,3,4,5,6 $. Parmi les nombres qui représentent cette couleur, $ 1,3 $ est la couleur avant / arrière et les autres sont les couleurs latérales.

En supposant que le tableau représentant cette couleur est $ p $, la correspondance entre les nombres (commençant par $ 0 $) et les faces de $ p $ est comme indiqué dans la figure ci-dessous.

Voici l'état complet dans l'exemple de cas.

1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3

L'entrée est donnée comme suit:

Nombre de puzzles saisis N(<=30)
Séquence d'états de puzzle séparés par des blancs p_1
p_2
...
p_n

Résolvons le problème.

Méthode intuitive mais moins polyvalente

La première méthode que vous pouvez proposer est une simulation simple et une recherche de priorité à la largeur. C'est moins polyvalent, mais relativement facile à mettre en œuvre (bien que la simulation de rotation soit très fastidieuse).

Estimez la quantité de calcul pour un puzzle. La prochaine étape que vous pouvez faire pour chaque état est de tourner soit vers le haut, vers le bas, vers la gauche ou vers la droite de 180 $, donc il y a 4 $ (après cela, nous allons concevoir cela pour réduire davantage le montant du calcul). Et comme vous pouvez l'obtenir à la main jusqu'à 8 $, le montant du calcul est au plus

O(4^8)=O(6.6\times10^4)

Ce sera. Même si 30 états de puzzle sont donnés, le montant du calcul sera $ O (2.0 \ times10 ^ 6) $, ce qui semble être dans le temps.

Maintenant, la partie délicate de cette méthode est la mise en œuvre du mouvement réel du puzzle. Cette fois, l'opération de rotation s'exprime en manipulant la séquence d'entrée $ p $ elle-même. Cette méthode est lourde et n'a pas de polyvalence, j'utiliserai donc une méthode différente plus tard. Les cubes Flop utilisent toujours une rotation de 180 $ degrés, vous pouvez donc l'implémenter en sélectionnant et en échangeant correctement les deux autocollants (éléments de la séquence). Le résultat de l'implémentation est ici (voir le lien pour le code) .. J'ai fait de la climatisation pour le moment. Le temps d'exécution était de 0,35 $ $ secondes et l'utilisation de la mémoire était de 14580 $ Ko.

** Bons points de cette méthode ** 1, si vous pouvez implémenter sans faire d'erreur dans où et où permuter, le reste n'est qu'une recherche de priorité de largeur, donc c'est une idée simple ** Mauvais points de cette méthode **

La mise en œuvre du lieu et du lieu d'échange n'est pas essentielle et paresseuse (j'ai aussi fait une erreur)
Puisqu'il s'agit d'une recherche avec priorité à la largeur, elle utilise la mémoire telle quelle
Pas polyvalent (écrire un programme qui résout un cube rubic normal de cette façon rend l'implémentation de la rotation très fastidieuse)

Améliorer la méthode intuitive

Maintenant, améliorons le programme précédent. En fait, ce programme peut facilement réduire la quantité de calcul.

** Ne tournez pas la même main que celle que vous aviez juste avant ** ** Par exemple, juste avant de monter, de descendre et de ne pas monter ** ** Si vous ne l'obtenez pas en 7 coups, la réponse est toujours 8 (car vous pouvez l'obtenir en 8 coups) **

En mettant en œuvre ces trois, vous pouvez réduire la quantité de calcul. Estimons spécifiquement la quantité de calcul pour un puzzle. Prenons le cas du maximum (8 mains). (* Ce n'est pas mathématiquement strict. En fait, le montant du calcul est susceptible d'augmenter légèrement)

O(4\times3^6-2\times5\times3^4)=O(2.1\times10^3)

Le montant du calcul dans le programme précédent était de $ O (6,6 \ times10 ^ 4) $, donc j'ai pu le réduire considérablement.

Le résultat que j'ai essayé est ici. Le temps d'exécution était de 0,08 $ secondes et la mémoire était de 6704 $ Ko. Le temps et la mémoire se sont considérablement améliorés (bien que le code ci-dessus soit AC).

Pensez à une méthode générique

Aperçu

Bien que ce soit une chute, il existe une méthode générale pour écrire des puzzles comme suit (ceux qui aiment Rubik Cube peuvent le savoir).

Pensez aux ** pièces ** au lieu des autocollants
Focus sur la ** position ** et ** l'orientation ** des pièces
Le puzzle étant composé de pièces de plusieurs formes, ** considérez la méthode ci-dessus pour chaque forme des pièces **

Pensons concrètement avec ce cube de disquette. Il existe trois types de cubes de disquette avec des autocollants (de couleur): «coin», «bord» et «centre». Pensons un peu plus à chacun.

coin Il bouge lorsqu'il est tourné. La direction (avant et arrière) change lors de la rotation

** Bord ** Il ne bouge pas même s'il est tourné (car il tourne autour de la partie de bord) La direction (avant et arrière) change lors de la rotation

Centre Ne bouge pas même en cas de rotation La direction ne change pas même si elle est tournée

Compte tenu de ces faits, nous pouvons voir que les trois types d'informations suivants sont tout ce qui est nécessaire pour représenter l'état du puzzle.

Positions de chacune des quatre pièces d'angle (CP = Corner Permutation)
Orientation de chacune des quatre pièces d'angle (CO = Corner Orientation)
Orientation de chacune des quatre parties de bord (EO = Edge Orientation)

** Addendum Bien qu'aucune preuve stricte n'ait été faite, il semble que CO sera automatiquement aligné si CP est aligné. Dans l'article, je le laisserai tel qu'il est écrit en tenant compte de CO, mais je publierai également un lien de soumission qui ne considère pas CO comme une note supplémentaire. ** **

Dans le processus de rotation réel, la baie est altérée selon les règles suivantes.

position Les numéros (noms) de 0 à 4 sont attribués aux positions des parties d'angle (supérieur gauche, supérieur droit, inférieur droit, inférieur gauche). Numérotez les pièces d'angle elles-mêmes de 0 à 4. Par exemple, le i-ème élément cp [i] du tableau CP cp signifie que la partie à l'emplacement i est nommée cp [i].

direction Numérotez les pièces d'angle / arête de 0 à 4 respectivement. Par exemple, 0 lorsque les pièces sont tournées vers l'avant (direction orientée lorsqu'elles sont alignées) et 1 lorsque les pièces sont tournées vers l'arrière. Par exemple, si le i-ème élément co [i] du réseau CO est 0, la partie à l'emplacement i est tournée vers le haut, et si elle est 1, elle est tournée vers l'arrière.

la mise en oeuvre

Il est plus facile d'utiliser des classes car les états d'un puzzle sont représentés par plusieurs tableaux. De plus, en définissant le numéro attribué à la position de la pièce, par exemple dans le sens des aiguilles d'une montre, vous n'avez pas à déterminer manuellement où déplacer lors de l'écriture du processus à faire pivoter. L'inconvénient de cette méthode est qu'il est un peu fastidieux de convertir les informations de couleur de chaque autocollant saisi en trois tableaux: CP, CO et EO.

résultat

Le code que j'ai écrit et le résultat de l'exécution sont ici. Le temps d'exécution était de 0,12 $ $ secondes et l'utilisation de la mémoire était de 6860 $ Ko.

** L'addendum AC a été fait même pour les programmes qui ne tiennent pas compte du CO. Le lien de soumission est ici. Le temps d'exécution était de 0,09 $ secondes et l'utilisation de la mémoire était de 6767 $ Ko. ** **

Réduisez la quantité de calcul-taille

Ici, utilisons la polyvalence qui est l'avantage du code à usage général mentionné précédemment pour effectuer un pré-calcul, puis utilisons-le pour élaguer et réduire la quantité de calcul.

L'élagage est réalisé en arrêtant la recherche quand on sait que le nombre de coups n'est pas dans le nombre de huit du dieu. Plus précisément, pour chaque état de CP, CO et EO, précalculez le nombre d'étapes pouvant être utilisées pour préparer uniquement CP pour CP, uniquement CO pour CO et uniquement EO pour EO. Et pendant la recherche de priorité de largeur,

** Nombre d'étapes effectuées jusqu'à présent + Nombre maximal d'étapes requises pour aligner indépendamment CP, CO et EO **

Est calculé, et lorsque cela dépasse le nombre de Dieu de 8 coups, la recherche ultérieure de ce nœud (état) est arrêtée.

Le résultat de la soumission qui implémente ceci est ici. Le temps d'exécution était de 0,16 $ $ secondes et l'utilisation de la mémoire était de 6804 $ Ko. ** L'addendum AC a été fait même pour les programmes qui ne tiennent pas compte du CO. Le lien de soumission est ici. Le temps d'exécution était de 0,13 $ $ secondes et l'utilisation de la mémoire était de 6544 $ Ko. ** **

Cette méthode d'élagage est similaire à cette fois car elle effectue un pré-calcul et calcule le numéro unique de chacune des séquences CP, CO et EO dans chaque recherche.

Le nombre de coups suivants pouvant être tournés à partir d'un nœud (état) est petit
La profondeur de recherche maximale (c'est-à-dire le nombre de Dieu) est peu profonde (petite)

Parfois, il n'y a pas beaucoup d'avantages. Cette fois, le temps d'exécution a un peu augmenté. Cependant, cet élagage présente des avantages incommensurables lorsque vous essayez de résoudre des énigmes plus complexes que les cubes de disquette.

Réduire l'utilisation de la mémoire-IDA *

Ce dont nous parlons ici est de savoir comment gérer l'utilisation ridicule de la mémoire liée à l'utilisation de la recherche avec priorité à la largeur lors de la résolution d'un autre puzzle qui n'est pas un cube de disquette. Par exemple, lorsque j'ai effectué une recherche de priorité de largeur avec un cube rubic 2x2x2, le programme que j'ai écrit mangeait environ 4 Go de mémoire.

Ce qui ressort ici est une méthode de recherche appelée IDA *. Pour plus de détails, l'article ici est détaillé et recommandé. Je présenterai une partie de cet article.

En un mot, IDA * est «Répéter la recherche de priorité de profondeur (DFS) avec une profondeur maximale limitée tout en augmentant la profondeur». Le mécanisme d'IDA * est d'oublier le nœud une fois recherché. Si vous oubliez le nœud, vous pouvez libérer de la mémoire.

Dans IDA *, si une recherche de priorité de profondeur est effectuée jusqu'à une profondeur de $ N-1 $ et qu'aucune solution n'est trouvée, la profondeur maximale est augmentée à $ N $ et la recherche est relancée depuis le début. En faisant cela,

Le résultat renvoyé est toujours l'effort le plus court (la procédure la plus courte peut être sortie avec un petit ajustement de l'implémentation)
Très faible utilisation de la mémoire

Il y a un avantage.

Cependant, pour les nœuds (états) peu profonds, la même recherche est répétée plusieurs fois, de sorte que la quantité de calcul augmente légèrement. Cependant, étant donné que l'état du puzzle augmente en tant que fonction exponentielle par rapport à la profondeur, l'augmentation de la quantité de calcul n'est pas si grande. Estimons spécifiquement le montant du calcul dans ce cas. Supposons que vous soyez dans un puzzle à 7 mains. Lorsque la recherche de priorité de largeur a été effectuée, le montant du calcul était d'environ $ O (2,1 \ times10 ^ 3) $ lorsque l'élagage était ignoré. Et dans l'IDA *

O(\Sigma_{i=1}^7 (4\times3^{i-1}-2\times(i-2)\times\mathrm{floor}(3^{i-3})))=O(3.3\times10^3)

est. Il n'y a pas beaucoup de différence en comparaison.

Le résultat de la mise en œuvre est ici. Le temps d'exécution est de 0,09 $ secondes, ce qui est plus rapide que le programme précédent. L'utilisation de la mémoire a été réduite à 6044 $ Ko, contre 6544 $ Ko pour les recherches à priorité largeur. ** L'addendum AC a été fait même pour les programmes qui ne tiennent pas compte du CO. Le lien de soumission est ici. Le temps d'exécution était de 0,07 $ secondes et l'utilisation de la mémoire était de 6036 $ Ko. ** **

Résumé

Merci d'avoir lu jusqu'ici. En particulier, la méthode introduite dans la seconde moitié est une méthode très générale, mais elle est trop excessive pour les cubes de disquette. Bien sûr, écrivez un programme qui résout les cubes rubic 2x2 et 3x3 en utilisant cette méthode, et découvrez la polyvalence de cette méthode. Pour 2x2, j'ai écrit Faisons un robot qui résout le Rubik Cube! 2 Algorithmes, 3x3 est de 7y2n [Écrivons un programme pour résoudre le cube rubic (Partie 2: recherche IDA *)](https: / Nous recommandons l'article /qiita.com/7y2n/items/24785b985e9c30862014).

Comment créer un programme pour résoudre le Rubik Cube à partir de PC Koshien 2014 Floppy Cube