ChromaOracle encuentra la solución más corta posible para cualquier puzzle de clasificación por color usando un algoritmo llamado búsqueda en anchura, o BFS. En lugar de adivinar o seguir heurísticas, el solucionador explora sistemáticamente cada secuencia posible de movimientos, las secuencias más cortas primero, hasta encontrar una que resuelva el puzzle. Esto garantiza que la solución devuelta use la menor cantidad de movimientos posible.
El puzzle como problema de búsqueda
Cada puzzle de clasificación por color —— ya sea Water Sort, Ball Sort o cualquier variante —— puede describirse como un problema de búsqueda. El tablero del puzzle en cualquier momento es un "estado": un arreglo específico de colores entre todos los tubos. Cada vertido o movimiento válido transforma un estado en otro.
¿Qué es la búsqueda en anchura?
La búsqueda en anchura es un método para explorar este mapa de estados en un orden muy específico: comprueba todos los estados que están a un movimiento del inicio, luego todos los estados a dos movimientos, luego tres, y así sucesivamente.
Este enfoque por capas es lo que garantiza la optimalidad. Como BFS explora todas las soluciones de cinco movimientos antes que cualquier solución de seis movimientos, la primera vez que alcanza el estado objetivo, necesariamente ha encontrado el camino más corto.
El proceso funciona así:
- Empieza con el estado inicial del tablero.
- Genera cada movimiento válido desde ese estado.
- Comprueba si alguno de esos nuevos estados es el estado resuelto.
- Si no, añade todos los nuevos estados a una cola y repite.
- Continúa hasta encontrar el objetivo o explorar todos los estados alcanzables.
Representación del espacio de estados
ChromaOracle representa cada tubo como una pila de colores, y el tablero completo como una colección de estas pilas. Para evitar explorar el mismo estado dos veces, el solucionador genera una clave canónica para cada estado.
Por qué BFS garantiza la solución más corta
La garantía proviene del orden de exploración. BFS procesa los estados estrictamente por su distancia al inicio. Por lo tanto, la primera vez que el solucionador alcanza el estado objetivo, ha llegado a través de un camino de longitud N, y no existe ningún camino de longitud menor que N.
BFS contra DFS
ChromaOracle también soporta búsqueda en profundidad (DFS) como alternativa. Las compensaciones son:
- BFS encuentra la solución más corta pero usa más memoria.
- DFS encuentra una solución más rápido en muchos casos y usa menos memoria, pero la solución puede no ser la más corta.
Cómo funciona el Modo Misterio
El Modo Misterio de ChromaOracle, diseñado para puzzles que contienen colores ocultos o desconocidos, maneja esto a través del análisis de permutaciones:
- El solucionador identifica todas las posiciones marcadas como desconocidas.
- Genera todas las asignaciones posibles de colores a esas posiciones.
- Resuelve cada puzzle resultante independientemente usando BFS.
- Analiza todos los conjuntos de soluciones para encontrar movimientos que sean seguros sin importar cuáles sean los colores ocultos.
Rendimiento y límites prácticos
El espacio de estados de un puzzle de clasificación por color crece exponencialmente. ChromaOracle se ejecuta completamente en el navegador usando TypeScript. Para la mayoría de los puzzles —— hasta unos diez colores —— BFS se completa en menos de un segundo.
Preguntas frecuentes
¿Por qué ChromaOracle tarda más en ciertos puzzles?
El tiempo de resolución depende del tamaño del espacio de estados.
¿Puede el solucionador no encontrar una solución?
Si existe una solución, BFS siempre la encontrará. Si BFS termina sin encontrar una solución, el puzzle es matemáticamente irresoluble.
¿Es la solución BFS siempre la mejor posible?
Sí. BFS garantiza la solución más corta en términos de número de movimientos.
¿Cómo sabe el Modo Misterio qué movimientos son seguros?
El Modo Misterio resuelve el puzzle para cada asignación posible de colores ocultos, luego compara todas las soluciones.