Forçage

Est-ce un hasard ? La controverse de Chaînes de contraintes

No. Chaînes de contraintes explore toutes les possibilités simultanément sans s'engager dans aucune hypothèse. Elles comparent toutes les branches et n'agissent que lorsque les branches convergent. Trois propriétés distinctives : exploration exhaustive, conclusion déterministe et correction prouvée. Chaînes de contraintes sont moins élégantes que les techniques basées sur les motifs, mais elles sont prouvées correctes.

Case Chaîne de contrainte

Commencez par une case à deux valeurs Case {A, B}. Propagez les implications pour chaque branche. Comparez les résultats. Contradiction : une branche est invalide, donc la Case doit être l'autre candidat. Convergence sur le placement : les deux branches imposent le même chiffre dans la même case éloignée Case. Convergence sur l'élimination : les deux branches éliminent le même candidat de la même case Case.

Chaîne de forçage régionale (Chaîne de forçage par chiffre)

Commencez par une des 2-3 positions d'un chiffre dans une maison. Explorez chaque position comme une branche. Mêmes trois types de déduction. Case force est efficace lorsque les cellules à deux valeurs ont des conséquences étendues. La force régionale est efficace lorsque la position d'un chiffre a des effets en chaîne importants.

Filet de contrainte : Augmenter le décompte des branches

Case Net de contrainte : cellules avec 3 à 6 candidats. Net de contrainte régionale : cases avec 4 à 6 positions possibles pour un chiffre. Plus de branches, plus coûteux, mais peut permettre de trouver des déductions Chaînes de contraintes ne peut pas. La logique est identique. Seul le nombre de branches diffère.

Le moteur de propagation

Chaque branche se propage à travers les singles nus, les singles cachés, Candidats verrouillés, et les paires nues, de manière itérative jusqu'à stabilité. Une seule hypothèse peut se propager à travers des dizaines d'étapes intermédiaires à travers toute la grille. Lorsque deux branches aboutissent à la même conclusion par des chemins complètement différents, la convergence prouve la conclusion avec certitude.

Les trois types de déduction

Contradiction : Une branche produit un état invalide. Cette hypothèse est fausse. La plus courante. Convergence sur placement : Toutes les branches obligent le même chiffre dans le même Case. Moins courante mais décisive. Convergence sur élimination : Toutes les branches éliminent le même candidat du même Case. Type le plus subtil.

Quand utiliser les techniques de contrainte

Dernier recours logique. Appliqué après l'échec de toutes les autres techniques. Chaînes de contraintes (2-3 branches) est essayé en premier. Le réseau contraint (3-6 branches) n'est utilisé que lorsque les chaînes échouent. Les deux sont de niveau 12 (extrême). Pour les solveurs informatiques, le forçage assure la complétude : la garantie que la logique seule peut résoudre n'importe quel puzzle valide.

Une note philosophique sur l'élégance et l'exactitude

Les techniques basées sur les motifs révèlent des relations structurelles et sont plus élégantes. Mais il existe des grilles valides qui nécessitent une logique de niveau forçage. Les techniques de forçage constituent le filet de sécurité qui attrape toutes les grilles que les techniques basées sur les motifs ne peuvent pas résoudre. La méthode la plus satisfaisante : essayer toutes les techniques basées sur les motifs en premier, puis recourir au forçage uniquement lorsque la grille le demande vraiment.

Résumé

Chaînes de contraintes et la technique du forcing net sont les méthodes logiques les plus puissantes, au niveau 12 (Extrême). Elles explorent toutes les possibilités à partir d'un point de départ, propagent les conséquences et comparent les résultats. Les déductions proviennent de contradiction, de convergence sur une position ou de convergence sur une élimination. Ce sont la dernière ressource avant le retour arrière par force brute, offrant une complétude pour tout puzzle Sudoku valide.