Je suis sûr que beaucoup de lecteurs se livraient parfois à des bêtises inutiles en classe au lieu d'écouter l'enseignant. C'est exactement ce que j'ai fait, et une façon de tuer le temps était de jouer sur papier. Le jeu de prévisualisation (dont le nom m'est encore inconnu) m'a paru particulièrement intéressant, mais il y a deux raisons: il ne nécessite pas de deuxième personne et il peut être complété! Certes, c'était extrêmement rare de le faire. Pendant longtemps, je me demandais à quel point la solution pouvait être simple et maintenant, après de nombreuses années, il ne sera pas difficile de la trouver par programme.
Les règles
Tout d'abord, il vaut la peine de décrire les règles. Le jeu commence par le champ suivant:
123456789
111213141
516171819
Ici, tous les nombres de 1 à 19 sont enregistrés caractère par caractère, à l'exception de 10. Les nombres sont situés de gauche à droite, ligne par ligne. Les règles sont assez simples - à chaque étape, vous devez barrer 2 chiffres qui correspondent aux critères suivants:
- les nombres doivent être identiques ou au total donner 10 (1 et 1, 3 et 7, 8 et 2, etc.);
- ils doivent soit être superposés, soit être disposés en série. Dans ce cas, les nombres déjà barrés sont ignorés.
L'une des options pour les premiers mouvements est illustrée ci-dessous:
1 23456789
1 11213141
5161718 19
#2345678 9
# 1 1213141
5161718##
#2345678#
##1213141
5161718##
Au moment où il n'y a plus de coups, tous les numéros non marqués sont ajoutés à la fin. Le jeu se termine lorsque le champ entier est barré.
#2345678#
##1213141
51 6 171 8 ##
23 4 567 8 12
131415161
718
#2345678#
##1213 1 41
5 1 # 1 71###
23#567#12
131415 1 61
718
#2345678#
##1213#41
5###71###
2 3 #567#12
1 3 1415#61
718
...
Le nombre de coups disponibles augmente rapidement, le jeu commence à se ramifier fortement. Souvent, le tableau devient si long qu'il déborde à la page suivante d'un cahier. Il est plus facile de démarrer un nouveau lot. Parfois, j'ai continué par persévérance, mais à la fin j'ai abandonné.
Cela soulève la question raisonnable - à quelle vitesse pouvez-vous terminer ce jeu? Dans l'enfance, il était possible de trouver une solution dans une colonne sur une feuille de cahier - c'est environ 40 lignes ou 360 caractères.
Je ne connais pas le moyen garanti de terminer le jeu. Il n'est absolument pas clair comment choisir une stratégie. Vous pouvez essayer de jouer vous-même si ce n'est pas le cas.
Solution
Comment cherche-t-on des solutions à ces problèmes? Je n'en suis pas sûr, mais j'ai choisi le buste habituel.
Nous avons besoin d'une file d'attente, consistant d'abord en une seule configuration initiale. À chaque étape, nous prenons la configuration suivante de la file d'attente, examinons tous les mouvements disponibles à partir de celle-ci et les ajoutons tous à la fin de la file d'attente ou nous déclarons vainqueur s'il n'y a pas de tels mouvements.
123456789 #23456789 12345678# 123456789 123456789 123456789 123456789 ...
111213141 #11213141 #11213141 ##1213141 1##213141 11#213141 11121314# ...
516171819 516171819 516171819 516171819 516171819 516#71819 51617181# ...
Si vous ne vous attardez pas sur la première solution disponible, alors cet algorithme produira toutes les solutions possibles (en présence d'une quantité infinie de RAM).
Dans la pratique, une telle approche naïve n'aidera pas du tout, du moins à cause des doublons qui apparaissent constamment dans la file d'attente. Par conséquent, certaines optimisations seront nécessaires, que j'expliquerai maintenant:
- Naturellement, les configurations doivent être mises en cache afin de ne pas les remettre en file d'attente. Cela augmentera considérablement l'utilisation de la mémoire, mais n'aidera pas à obtenir une solution dans un délai raisonnable. De plus, la question de la comparaison des configurations se pose fortement. Étant donné que deux configurations gagnantes de la même taille seront toujours constituées uniquement de numéros barrés, une autre façon de les distinguer est nécessaire, sinon toutes les solutions ne seront pas trouvées;
- pour rendre la recherche significative et rapide, il est préférable d'utiliser une file d'attente prioritaire. Moins il y a de nombres sur le terrain (y compris barrés), plus cette configuration doit être envisagée tôt;
- si vous avez besoin de plusieurs solutions, mais plusieurs, il est préférable de limiter le nombre maximum de chiffres sur le terrain, la recherche émettra des solutions beaucoup plus tôt.
La réponse
Si tout est correct, il s'avère que la solution minimale ne comprend que 68 caractères ou 8 lignes!
Je vais l'apporter sous forme de gif-animation. Certains mouvements ont été collés en un pour réduire le nombre d'images:
Je suis honnête, j'ai été frappé par la brièveté de cette décision. Mais peut-être que cette chance et d'autres décisions ne seront pas prises bientôt et seront très longues?
Non, les décisions ne sont pas rares du tout. Des réponses rapides se trouvent dans les longueurs de 72, 74 et 76. Et 4 solutions fondamentalement différentes avec une longueur de 80. En général, j'ai réussi à trouver 30 solutions jusqu'à 90 de longueur (inclus), et si j'augmente la frontière à 100, alors il y aura 170 solutions. mais les chercher devient plus cher.
Sous le spoiler, la solution optimale est décrite en détail:
Texte masqué 123456789 111213141 516171819 123456789 111213141 5161718## 123456789 1##213141 5161718## 12345678# 1##21314# 5161718## #2345678# ###21314# 5161718## #234567## ####1314# 5161718## #234567## ####1314# 5161718## 234567131 45161718 #234567## ####1314# 51#1718## 23#567131 45161718 #234567## ####1314# 51#171### #3#567131 45161718 #234567## ####1314# 51#171### #3#567#31 451617#8 #234567## ####1314# 51#171### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 571356145 16178 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 57#356145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 5###56145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 #####6145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 34567131# ######145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3456713## #######45 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 451617### 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 45161#### ##56713## #######45 1##78 #234567## ####1314# 5###7#### #3#56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# 5######## ###56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##56##### #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##5###### ########5 1##78 #234567## ####1314# ######### ####6###1 45161#### ######### ######### 1##78 #234567## ####131## ######### ########1 45161#### ######### ######### 1##78 #234567## ####13### ######### ######### 45161#### ######### ######### 1##78 #234567## #####3### ######### ######### 4516##### ######### ######### 1##78 #23456### ######### ######### ######### 4516##### ######### ######### 1##78 #2345#### ######### ######### ######### #516##### ######### ######### 1##78 #234##### ######### ######### ######### ##16##### ######### ######### 1##78 #23###### ######### ######### ######### ##1###### ######### ######### 1##78 #23###### ######### ######### ######### ######### ######### ######### ###78 #2####### ######### ######### ######### ######### ######### ######### ####8 ######### ######### ######### ######### ######### ######### ######### #####
Mon code de solution Java peut être consulté sur ce lien , mais je vous préviens qu'il est terrible, car écrit à l'origine pas pour publication. Dans sa forme actuelle, il trouve toutes les solutions jusqu'à 70 caractères (c'est-à-dire une seule solution). Ceci est facile à résoudre en jouant avec les conditions du code.
Merci de votre attention!