La app «Sort Puzzle» comprueba con el ordenador que un problema se puede resolver antes de mostrarlo. El siguiente movimiento de la «Pista» también es el primero del procedimiento que encuentra el mismo solucionador. Aquí te explicamos cómo funciona.

Seguir las situaciones y los movimientos

Llamamos situación al estado del tablero (qué colores hay en cada tubo). Al hacer un movimiento, se pasa a otra situación. Si, siguiendo los movimientos desde la situación inicial, se llega a una situación ordenada, el camino recorrido es la solución.

La forma de buscar más directa es la búsqueda en anchura: se despliegan todas las situaciones a las que se llega en 1 movimiento, después todas las que se alcanzan en 2… Siempre encuentra una solución con el mínimo de movimientos, pero cuando hay muchos colores, el número de situaciones que examinar es enorme.

Una medida de «lo lejos que está» de quedar ordenado

Por eso la app calcula para cada situación una medida de lo lejos que está de quedar ordenada y examina primero las situaciones que parecen más cercanas. La medida es la suma de estas dos cosas:

  1. Número de cortes de color dentro de los tubos: mirando de abajo arriba, cuántas veces cambia el color.
  2. Coincidencias en el fondo: si un mismo color está en el fondo de varios tubos, ese número menos 1.
123456

En este tablero, los cortes de color son 2 en el tubo 1, 2 en el 2, 3 en el 3 y 3 en el 4, 10 en total. El celeste está en el fondo del 3 y del 4, así que las coincidencias en el fondo son 1. La medida es 11. En una situación ordenada no hay cortes ni coincidencias, así que la medida es 0.

La medida no es mayor que el mínimo de movimientos

Esta medida tiene una buena propiedad: con un movimiento, la medida no baja en más de 1.

  • Con un vertido, los cortes del tubo de origen bajan como mucho en 1. El destino es sobre el mismo color o un tubo vacío, así que sus cortes ni suben ni bajan.
  • Que un tubo quede vacío y baje en 1 la coincidencia del fondo solo ocurre cuando se mueve la última tanda de ese tubo, y entonces los cortes no bajan.

Es decir, un tablero con medida 11 necesita al menos 11 movimientos. Probando más de 120.000 movimientos en distintos tableros, no hubo ningún movimiento que bajara la medida en 2 o más de una vez. El mínimo de movimientos del tablero de arriba es justo 11.

Búsqueda A* con peso

La app le da a cada situación la puntuación «movimientos hasta ahora + 3 × medida» y examina primero las de puntuación menor. Esto se llama búsqueda A* (A estrella) con peso.

  • Con peso 1 (la búsqueda A* normal), como la medida es una cota inferior del mínimo de movimientos, siempre se encuentra una solución con el mínimo de movimientos.
  • Con peso 3, como se examinan primero las situaciones de medida pequeña, la solución se encuentra mucho antes. A cambio, a veces la solución es algo más larga que el mínimo.

Con 20 problemas de cada tipo creados como lo hace la app, comparamos el número de situaciones examinadas hasta quedar ordenado y los movimientos de la solución encontrada (la búsqueda en anchura de ★3 no se ha contado porque hay demasiadas situaciones).

★1 (4 colores · 2 vacíos)Situaciones examinadasMovimientos de la solución
Búsqueda en anchura53711,8
A* (peso 1)20311,8
A* (peso 3)3911,9
★2 (6 colores · 2 vacíos)Situaciones examinadasMovimientos de la solución
Búsqueda en anchura293418,1
A* (peso 1)62218,1
A* (peso 3)6418,8

En ambos casos es la media de 20 problemas. Con peso 3, la solución se encuentra con unas decenas de veces menos situaciones que la búsqueda en anchura, y los movimientos aumentan solo un poco.

Trucos para examinar menos movimientos

El solucionador de la app también reduce las situaciones que examina con estos trucos:

  • No distinguir el orden de los tubos: si el contenido de los tubos es el mismo, aunque el orden sea distinto, se trata como la misma situación.
  • No examinar movimientos inútiles: se descartan los movimientos de un tubo de un solo color a un tubo vacío (la forma no cambia) y los movimientos al segundo tubo vacío y siguientes (dan la misma situación que con el primero).
  • Buscar solo con movimientos de «Verter»: también en los problemas de «Apilar» se comprueba si se pueden resolver con movimientos de verter (Diferencias entre «Verter» y «Apilar»).
  • Poner un límite: si tras examinar 60.000 situaciones no se encuentra, se da por «no se sabe» y ese reparto no se usa.

Este solucionador cubre tanto la «comprobación de que se puede resolver» al crear los problemas (Cómo se crean problemas que siempre tienen solución) como la «Pista» (Cómo usar la pista). La idea del color del fondo también se explica en ¿Por qué color empezar?.