¿Cuántos movimientos hacen falta como mínimo para resolver un Sort Puzzle? Con el tamaño de ★1 de la app «Sort Puzzle» (4 colores, 2 tubos vacíos), podemos examinar todos los repartos. Contamos el mínimo de movimientos de todos los repartos con movimientos de «Verter».
Cómo lo comprobamos
- Examinamos solo los «repartos justos», sin ningún tubo con 3 o más colores iguales seguidos (la app solo muestra estos repartos).
- Consideramos iguales los repartos que solo difieren en el orden de los tubos o en los colores cambiados. Quedan 89.675 tipos (¿De cuántas formas se puede repartir?).
- En cada reparto, desplegamos todas las situaciones a las que se llega en 1 movimiento, en 2 movimientos… y hallamos el número de movimientos con el que se ordena por primera vez (búsqueda en anchura).
Distribución del mínimo de movimientos
| Mínimo de movimientos | Tipos de reparto |
|---|---|
| 5 | 3 |
| 6 | 8 |
| 7 | 124 |
| 8 | 741 |
| 9 | 3.523 |
| 10 | 11.070 |
| 11 | 21.321 |
| 12 | 26.778 |
| 13 | 19.271 |
| 14 | 6.635 |
| 15 | 197 |
| 16 | 4 |
Lo más habitual son 12 movimientos, y entre 10 y 13 está más del 80 % del total. Solo hay 3 tipos de reparto que se resuelven en 5 movimientos y 4 que necesitan 16.
(Las cifras de aquí son «tipos». La probabilidad con la que la app reparte cada tipo varía un poco de uno a otro.)
El tablero más corto (5 movimientos)
En todos los tubos hay dos colores iguales apilados. Con los 2 tubos vacíos se ordena en 5 movimientos.
El tablero que más movimientos exige (16)
Los tubos 1 y 2, y los tubos 3 y 4, tienen exactamente la misma disposición. En todos los tubos, los colores contiguos son todos distintos, y el rojo y el lima están cada uno en el fondo de 2 tubos.
Ver los 16 movimientos
Cómo hallar una cota inferior
Sin probarlo todo, solo mirando el tablero puedes saber una cota inferior (un número por debajo del cual no se puede bajar) del mínimo de movimientos.
- Cuenta los cortes de color dentro de los tubos.
- Si un mismo color está en el fondo de varios tubos, suma «ese número menos 1».
Este total no puede ser mayor que el mínimo de movimientos, porque cada vez que viertes baja como mucho en 1 (Resolver con el ordenador).
- Tablero de 5 movimientos: tiene 4 cortes y el rojo está en el fondo de 2 tubos, así que sumas 1 y la cota inferior es 5. Es justo el mínimo.
- Tablero de 16 movimientos: tiene 12 cortes y el rojo y el lima están cada uno en el fondo de 2 tubos, así que sumas 2 y la cota inferior es 14. En realidad hacen falta 16.
De los 89.675 tipos, en 38.571 (cerca del 43 %) la cota inferior coincidía exactamente con el mínimo de movimientos. En el resto hacen falta más que la cota inferior.
En tableros más grandes
Cuando hay más colores, hay demasiados repartos para examinarlos todos. Con problemas creados como lo hace la app, la media del mínimo de movimientos en 20 problemas fue de 11,8 en ★1 y de 18,1 en ★2 (6 colores). Desde ★3, incluso hallar el mínimo de un solo problema lleva tiempo.
La «Pista» de la app no te da el mínimo de movimientos, sino una forma de resolver que se encuentra rápido. Si quieres retarte con el mínimo, piensa tú el procedimiento tomando la cota inferior como referencia (Cómo usar la pista).
