My two year old taught me constraint solving
L'auteur décrit comment, en jouant au train Brio avec son fils de deux ans, il s'est posé la question algorithmique de savoir si un ensemble de pièces pouvait être assemblé en un réseau totalement fermé. Un premier solveur par backtracking exhaustif place récursivement des pièces sur des connecteurs ouverts et résout de petits cas rapidement mais souffre d'une explosion exponentielle d'états et d'absence de mémoire entre impasses. La formulation comme problème de satisfaction de contraintes (CSP) ajoute propagation et backjumping et s'améliore notablement seulement après l'introduction de contrôles globaux de faisabilité, tandis que le simple forward checking a parfois empiré la recherche. La réduction en SAT exige de recenser au préalable des positions atteignables puis d'encoder chaque placement en variable booléenne et, grâce à l'apprentissage de clauses (CDCL) et à une boucle d'interdiction des sous-ensembles déconnectés, permet de maximiser et de sélectionner les pièces au prix d'un coût mémoire et temporel plus élevé et d'une complétude limitée aux positions explorées. La leçon est que les formulations diffèrent selon la question posée, que des contraintes globales pertinentes sont cruciales pour pruner efficacement l'espace de recherche, et que SAT offre une mémoire des échecs utile quand on accepte des compromis en performance et en champ de recherche.