Si le problème est vraiment difficile (je ne pense pas qu'il le soit), maintenir la cohérence d'arc pendant la recherche peut être payant. En gros, ça consiste à supprimer du backtrack toutes les valeurs qui ne peuvent pas s'étendre à une solution locale --par exemple, les cases qui n'ont plus de voisins libres-- et donc a fortiori à une solution tout court. Si de cette manière on vide un domaine, on sait que la dernière valeur instanciée est inconsistante, donc on peut la supprimer (et propager cette suppression).
L'intérêt de supprimer des valeurs, c'est qu'ensuite on évite de les explorer de manière répétitive.
[^] # Arc Consistency
Posté par Polaris . En réponse au journal Deplacement du cheval. Évalué à 1.
L'intérêt de supprimer des valeurs, c'est qu'ensuite on évite de les explorer de manière répétitive.