ChromaOracle trouve la solution la plus courte possible à n'importe quel puzzle de tri par couleur en utilisant un algorithme appelé parcours en largeur, ou BFS. Au lieu de deviner ou de suivre des heuristiques, le solveur explore systématiquement chaque séquence de coups possible, les séquences les plus courtes d'abord, jusqu'à en trouver une qui résout le puzzle.
Le puzzle comme problème de recherche
Chaque puzzle de tri par couleur —— qu'il s'agisse de Water Sort, Ball Sort ou de toute variante —— peut être décrit comme un problème de recherche. Le plateau du puzzle à tout moment est un "état" : un arrangement spécifique de couleurs sur tous les tubes. Chaque versement ou coup valide transforme un état en un autre.
Qu'est-ce que le parcours en largeur?
Le parcours en largeur est une méthode pour explorer cette carte d'états dans un ordre très spécifique : il vérifie tous les états qui sont à un coup du départ, puis tous les états qui sont à deux coups, puis trois, et ainsi de suite.
Cette approche en couches est ce qui garantit l'optimalité. Comme BFS explore toutes les solutions à cinq coups avant toute solution à six coups, la première fois qu'il atteint l'état cible, il a nécessairement trouvé le chemin le plus court.
Le processus fonctionne comme ceci:
- Commencer avec l'état initial du plateau.
- Générer chaque coup valide à partir de cet état.
- Vérifier si l'un de ces nouveaux états est l'état résolu.
- Sinon, ajouter tous les nouveaux états à une file et répéter.
- Continuer jusqu'à ce que la cible soit trouvée ou que tous les états atteignables aient été explorés.
Représentation de l'espace d'états
ChromaOracle représente chaque tube comme une pile de couleurs, et le plateau complet comme une collection de ces piles. Pour éviter d'explorer le même état deux fois, le solveur génère une clé canonique pour chaque état.
Pourquoi BFS garantit la solution la plus courte
La garantie vient de l'ordre d'exploration. BFS traite les états strictement par leur distance du départ. Par conséquent, la première fois que le solveur atteint l'état cible, il y est arrivé via un chemin de longueur N, et aucun chemin de longueur inférieure à N n'existe.
BFS contre DFS
ChromaOracle prend également en charge le parcours en profondeur (DFS) comme alternative. Les compromis sont:
- BFS trouve la solution la plus courte mais utilise plus de mémoire.
- DFS trouve une solution plus rapidement dans de nombreux cas et utilise moins de mémoire, mais la solution peut ne pas être la plus courte.
Comment fonctionne le Mode Mystère
Le Mode Mystère de ChromaOracle, conçu pour les puzzles contenant des couleurs cachées ou inconnues, gère cela par l'analyse de permutations:
- Le solveur identifie toutes les positions marquées comme inconnues.
- Il génère chaque attribution possible de couleurs à ces positions.
- Il résout chaque puzzle résultant indépendamment en utilisant BFS.
- Il analyse tous les ensembles de solutions pour trouver des coups qui sont sûrs quelles que soient les couleurs cachées.
Performance et limites pratiques
L'espace d'états d'un puzzle de tri par couleur croît exponentiellement. ChromaOracle s'exécute entièrement dans votre navigateur en utilisant TypeScript. Pour la plupart des puzzles —— jusqu'à environ dix couleurs —— BFS se termine en moins d'une seconde.
Questions fréquemment posées
Pourquoi ChromaOracle prend-il plus de temps sur certains puzzles?
Le temps de résolution dépend de la taille de l'espace d'états.
Le solveur peut-il échouer à trouver une solution?
Si une solution existe, BFS la trouvera toujours. Si BFS termine sans trouver de solution, le puzzle est mathématiquement insoluble.
La solution BFS est-elle toujours la meilleure possible?
Oui. BFS garantit la solution la plus courte en termes de nombre de coups.
Comment le Mode Mystère sait-il quels coups sont sûrs?
Le Mode Mystère résout le puzzle pour chaque attribution possible de couleurs cachées, puis compare toutes les solutions.