Estoy seguro de que muchos de los lectores a veces se dedican a tonterías inútiles en el aula en lugar de escuchar al maestro. Hice exactamente eso, y una forma de matar el tiempo era jugar en papel. El juego de vista previa (cuyo nombre aún desconozco) me pareció especialmente interesante, pero hay dos razones: ¡no requiere una segunda persona y se puede completar! Es cierto que era extremadamente raro hacer esto. Durante mucho tiempo me preguntaba qué tan simple puede ser la solución, y ahora, después de muchos años, no será difícil encontrarla mediante programación.
Las reglas
Primero, vale la pena describir las reglas. El juego comienza con el siguiente campo:
123456789
111213141
516171819
Aquí, todos los números del 1 al 19 se registran carácter por carácter, con la excepción de 10. Los números se encuentran de izquierda a derecha, línea por línea. Las reglas son bastante simples: en cada paso debe tachar 2 números que corresponden a los siguientes criterios:
- los números deben ser iguales o en total dar 10 (1 y 1, 3 y 7, 8 y 2, etc.);
- deben estar uno encima del otro o estar dispuestos en serie. En este caso, los números ya tachados se ignoran.
A continuación se muestra una de las opciones para los primeros movimientos:
1 23456789
1 11213141
5161718 19
#2345678 9
# 1 1213141
5161718##
#2345678#
##1213141
5161718##
En el momento en que no hay más movimientos, todos los números sin marcar se agregan al final. El juego termina cuando se tacha todo el campo.
#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
...
El número de movimientos disponibles aumenta rápidamente, el juego comienza a ramificarse fuertemente. A menudo, la tabla se vuelve tan larga que se desborda a la página siguiente en un cuaderno. Es más fácil comenzar un nuevo lote. A veces seguí por perseverancia, pero al final me di por vencido.
Esto plantea la pregunta razonable: ¿qué tan rápido puedes terminar este juego? En la infancia, era posible encontrar una solución en una columna en una hoja de cuaderno: esto es aproximadamente 40 líneas o 360 caracteres.
No sé la forma garantizada de completar el juego. No está completamente claro cómo elegir una estrategia. Puedes intentar jugarlo tú mismo si no lo has hecho.
Solución
¿Cómo se buscan soluciones a tales problemas? No estoy seguro, pero elegí el busto habitual.
Necesitamos una cola, que primero consiste solo en una única configuración inicial. En cada paso, tomamos la siguiente configuración de la cola, observamos todos los movimientos disponibles y los agregamos todos al final de la cola o nos declaramos ganadores si no hay tales movimientos.
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 no se detiene en la primera solución disponible, este algoritmo producirá todas las soluciones posibles (en presencia de una cantidad infinita de RAM).
En la práctica, un enfoque tan ingenuo no ayudará en absoluto, al menos debido a los duplicados que aparecen constantemente en la cola. Por lo tanto, se requerirán algunas optimizaciones, que ahora explicaré:
- Naturalmente, las configuraciones deben almacenarse en caché para no volver a ponerlas en cola. Esto aumentará en gran medida el uso de memoria, pero aún no ayudará a obtener una solución en un período de tiempo razonable. Además, la cuestión de comparar configuraciones surge de manera aguda. Dado que dos configuraciones ganadoras del mismo tamaño siempre consistirán solo en números tachados, entonces se necesita una forma adicional de distinguirlos, de lo contrario no se encontrarán todas las soluciones;
- Para que la búsqueda sea significativa y rápida, es mejor usar una cola prioritaria. Cuantos menos números en el campo (incluido tachado), antes se debe considerar dicha configuración;
- Si necesita más de una solución, pero muchas, es mejor limitar el número máximo de números en el campo, la búsqueda emitirá soluciones mucho antes.
La respuesta
Si todo es correcto, ¡resulta que la solución mínima consta de solo 68 caracteres u 8 líneas!
Lo traeré en forma de gif-animation. Algunos movimientos se pegaron en uno para reducir el número de fotogramas:
Honestamente, me sorprendió lo breve que es esta decisión. ¿Pero tal vez esta suerte y otras decisiones no se cumplirán pronto y serán muy largas?
No, las decisiones no son raras en absoluto. Las respuestas rápidas se encuentran en longitudes de 72, 74 y 76. Y 4 soluciones más fundamentalmente diferentes con una longitud de 80. En general, logré encontrar 30 soluciones de hasta 90 de longitud (inclusive), y si aumento el límite a 100, entonces habrá 170 soluciones. pero buscarlos se vuelve más caro.
Bajo el spoiler, la solución óptima se describe en detalle:
Texto oculto 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 ######### ######### ######### ######### ######### ######### ######### #####
Mi código de solución Java se puede ver en este enlace , pero le advierto que es terrible, porque originalmente escrito no para publicación. En su forma actual, encuentra todas las soluciones de hasta 70 caracteres (es decir, solo una solución). Esto es fácil de solucionar jugando con las condiciones del código.
Gracias por su atencion!