El rompecabezas Neutralizador

Cuando vi el vídeo pebbling a chessboard de Numberphile, pensé que podría usar la mecánica de juego que se describe para crear un puzle. La idea básica era la clonación. Era un concepto atractivo y fácil de implementar programáticamente.

En el vídeo puedes ver que el juego descrito es bastante diferente de Neutralizador. Consiste en un solo tipo de elemento activo que Zvezdelina Stankova llama guijarro o clón, y un objetivo diferente, a saber, escapar de una prisión. También el tablero es infinito, mientras que en Neutralizator se juega sobre un tablero 8x8 de ajedrez clásico. En cambio, el rompecabezas Neutralizator tiene dos tipos de piezas y el objetivo es acabar con todas.

Al principio quería crear un rompecabezas con el mismo objetivo, pero como puedes ver en el vídeo, se trata de un objetivo imposible. Así que para poder jugar y ganar, añadí un segundo elemento clonador que interactúa con el primero. Creo que la forma más evidente de interacción para evitar el bloqueo en el rompecabezas es la cancelación: cuando se encuentran dos partículas de tipos diferentes, se cancelan mutuamente.

Entonces sólo quedaba una cosa más: escoger la metáfora para el tema del puzle. No es muy creativo que digamos, pero partículas electrón-positrón es lo primero que me vino a la cabeza. (Explicar el proceso de clonación es otra historia.)

Dos partículas iniciales en un tablero 8x8 de ajedrez, colocadas en esquinas opuestas.
Posición inicial del rompecabezas Neutralizator.
Estado intermedio del puzzle con positrones clonados.
La mecánica del juego es la misma que la de los clones de Stankova.

Este enigma online ofrece poca resistencia: puedes resolverlo clonando y cancelando alegremente las partículas. Pero cuidado con los estados que te conducen a posiciones de partida perdida. Siempre necesitas una partícula negativa en la zona superior derecha de cada partícula positiva y viceversa. En el siguiente ejemplo hay una partícula positiva que no tiene ninguna partícula negativa en su zona de avance, por lo que el rompecabezas no se podrá resolver.

Un estado del rompecabezas que no es resoluble.
Fin del juego: si llegas a esta posición, puedes seguir jugando, ¡pero no podrás resolver el rompecabezas!

Solución

El objetivo del rompecabezas es cancelar todas las partículas. No es muy difícil. Como en otros juegos en puzzlopia, lo suyo es resolverlo en el menor número de pasos, y eso es otra historia.

Resulta que Jaap Scherphuis ha encontrado un algoritmo para resolver el rompecabezas óptimamente para todos los tableros cuadrados de lados n > 2. (Gracias también a astralfenix y ffao por sus contribuciones).

Animación de los primeros pasos de la solución óptima para resolver Neutralizador 8x8
Patrón Zig-zag del algoritmo de Jaap Scherphuis: primeros pasos, luego repetir con las partículas negativas.

Aquí están los pasos de las soluciones óptimas de versiones cuadradas del rompecabezas (puedes ver que el valor es 6(n-2) para un tablero nxn cuando n > 2):

Longitudes de las soluciones óptimas

  • Tablero 2x2 2
  • Tablero 3x3 6
  • Tablero 4x4 12
  • Tablero 5x5 18
  • Tablero 6x6 24
  • Tablero 7x7 30
  • Tablero 8x8 36

Variaciones

Siempre es interesante pensar en posibles variaciones de un rompecabezas, y en este caso creo que se pueden generar bastantes (aunque algunas irresolubles). Un ejemplo es modificar las condiciones iniciales, como sigue:

Esta variación consiste en sobrecargar el estado inicial.
Esta variación añade partículas al estado inicial. ¡Parece que hay más trabajo que realizar para resolver el puzzle!
Jugar a Neutralizador II

Si rompemos el equilibrio inicial entre partículas positivas-negativas y no dejamos suficiente espacio para el proceso de clonado, puede que acabemos con un rompecabezas irresoluble:

Una variación con partículas +/- descompensadas.
¡Ni idea de si es resoluble! (Avísame si te da por explorar todos los estados y llegas a una conclusión).

Otras variaciones podrían incluir añadir nuevos tipos de elementos clonantes, o que los dos tipos de partículas se clonaran hacia arriba-derecha (?). ¿Y si un tipo de partícula necesita dos del otro tipo para cancelarse? Variación del tablero: se podrían probar versiones hexagonales y triangulares. Como ves, ¡eso es la historia interminable!

Si tienes alguna idea, ¡compártela!

Comentarios (0)

    Nuevo comentario

    Por favor, inicia sesión para poder comentar.