O ChromaOracle encontra a solução mais curta possível para qualquer puzzle de classificação por cor usando um algoritmo chamado busca em largura, ou BFS. Em vez de adivinhar ou seguir heurísticas, o solucionador explora sistematicamente cada sequência possível de movimentos, sequências mais curtas primeiro, até encontrar uma que resolva o puzzle.
O puzzle como um problema de busca
Cada puzzle de classificação por cor —— seja Water Sort, Ball Sort ou qualquer variante —— pode ser descrito como um problema de busca. O tabuleiro do puzzle a qualquer momento é um "estado": um arranjo específico de cores em todos os tubos. Cada despejamento ou movimento válido transforma um estado em outro.
O que é busca em largura?
Busca em largura é um método para explorar este mapa de estados em uma ordem muito específica: ela verifica todos os estados que estão a um movimento do início, depois todos os estados a dois movimentos, depois três, e assim por diante.
Esta abordagem em camadas é o que garante a otimalidade. Como BFS explora todas as soluções de cinco movimentos antes de qualquer solução de seis movimentos, na primeira vez que alcança o estado alvo, necessariamente encontrou o caminho mais curto.
O processo funciona assim:
- Comece com o estado inicial do tabuleiro.
- Gere cada movimento válido a partir desse estado.
- Verifique se algum desses novos estados é o estado resolvido.
- Se não, adicione todos os novos estados a uma fila e repita.
- Continue até encontrar o objetivo ou explorar todos os estados alcançáveis.
Representação do espaço de estados
O ChromaOracle representa cada tubo como uma pilha de cores, e o tabuleiro completo como uma coleção dessas pilhas. Para evitar explorar o mesmo estado duas vezes, o solucionador gera uma chave canônica para cada estado.
Por que BFS garante a solução mais curta
A garantia vem da ordem de exploração. BFS processa estados estritamente por sua distância do início. Portanto, na primeira vez que o solucionador alcança o estado alvo, chegou através de um caminho de comprimento N, e nenhum caminho de comprimento menor que N existe.
BFS contra DFS
O ChromaOracle também suporta busca em profundidade (DFS) como alternativa. Os trade-offs são:
- BFS encontra a solução mais curta mas usa mais memória.
- DFS encontra uma solução mais rapidamente em muitos casos e usa menos memória, mas a solução pode não ser a mais curta.
Como o Modo Mistério funciona
O Modo Mistério do ChromaOracle, projetado para puzzles contendo cores ocultas ou desconhecidas, lida com isso através de análise de permutações:
- O solucionador identifica todas as posições marcadas como desconhecidas.
- Gera todas as atribuições possíveis de cores para essas posições.
- Resolve cada puzzle resultante independentemente usando BFS.
- Analisa todos os conjuntos de soluções para encontrar movimentos que sejam seguros independentemente das cores ocultas.
Desempenho e limites práticos
O espaço de estados de um puzzle de classificação por cor cresce exponencialmente. O ChromaOracle é executado inteiramente no seu navegador usando TypeScript. Para a maioria dos puzzles —— até cerca de dez cores —— BFS termina em menos de um segundo.
Perguntas frequentes
Por que o ChromaOracle leva mais tempo em certos puzzles?
O tempo de resolução depende do tamanho do espaço de estados.
O solucionador pode falhar em encontrar uma solução?
Se uma solução existe, BFS sempre a encontrará. Se BFS termina sem encontrar uma solução, o puzzle é matematicamente insolúvel.
A solução BFS é sempre a melhor possível?
Sim. BFS garante a solução mais curta em termos de número de movimentos.
Como o Modo Mistério sabe quais movimentos são seguros?
O Modo Mistério resolve o puzzle para cada atribuição possível de cores ocultas, depois compara todas as soluções.