6. Quelques exemples de résolution
Voici quelques résultats trouvés par l'algorithme avec une indication du nombre d'étape qui ont été nécessaires.
7. Importance de l'heuristique
Il existe surement plusieurs heuristiques possibles. Que se passe-t-il si au lieu de compter les lignes et colonnes non entièrement couvertes, on faisait la même chose avec les segments horizontaux et verticaux ? Un segment horizontal est une ligne horizontale sans obstacle. Dans le premier labyrinthe, on a un seul segment sur la première ligne, mais deux dans chacune des suivantes.
Le résultat est surprenant. Ce nouvel algorithme résoud la 4ème grille en un temps record (seulement 119 configurations étudiées), mais il ne trouve pas la meilleure solution pour la seconde et la troisième. Pouvez-vous expliquer ceci ?