I built a constraint satisfaction problem (CSP) solver in Java 21, and I exposed it as a Spring Boot REST service. A CSP has variables, a set of allowed values for each one, and constraints between them. I wrote every algorithm myself, without a CSP library.

The service solves N-Queens, Sudoku, graph coloring, and number puzzles such as SEND + MORE = MONEY. A browser page shows the search live over a WebSocket.

Backtracking is complete, so it can prove that no solution exists. A min-conflicts local search gives up that guarantee, but it places 1,000 queens in about 15 ms.

The backtracking search assigns one variable at a time, and it undoes any choice that leads to a dead end. Several techniques make it faster.

• Forward checking runs after each assignment. It removes conflicting values from neighboring variables and stops early when one runs out of values.
• AC-3 runs once before the search. It makes every constraint arc consistent, which means each remaining value has a compatible value in each neighbor.
• MRV (minimum remaining values), the default ordering, picks the variable with the fewest values left, and it breaks ties by the number of constraints.
• Dom/WDeg divides the number of values left by a weighted count of constraints. A constraint gets more weight each time it empties a variable's values.
• A DomainTrail records changes, so a dead end rolls back only the BitSet domains that changed.

For N-Queens with N of 50 or more, the API switches to min-conflicts. It starts from a greedy placement, and it then moves conflicted queens to their least conflicted column until no conflicts remain.

The live view streams search events over STOMP, a messaging protocol on top of WebSocket. Board updates are capped at about 30 per second.

• I replaced full domain copies with a trail. The first version copied every domain at every search node, which allocated memory in proportion to the problem size at each node. My design notes report that the trail made each node about twice as cheap.
• Forward checking is the propagation used during search, and AC-3 runs only before it. Running arc consistency at every node (MAC) removes more values, but it reruns AC-3 each time. My notes record forward checking with good variable ordering as the better default.
• The API picks a strategy by problem size. Backtracking stays the default for small boards, because it can list every solution. Min-conflicts handles large N-Queens, where backtracking slows down badly.

Three bugs failed silently, and the tests didn't catch them at first.

• The value selectors returned the live domain. The solver pruned that domain while it explored the first value, so the remaining choices could change under the loop and the search became incomplete. The selectors now loop over a snapshot.
• Under MAC, propagation doesn't enforce a constraint that exposes no arcs, i.e., pairs of variables that AC-3 can check. The sum in a number puzzle is such a constraint. The solver now checks every constraint on each complete assignment.
• Dom/WDeg stored a weight of 1.0 on the first failure, which is the same as the default weight. The first failure now raises the weight to 2.0.

The 200-Queens test also ran about twice as slow in the full test suite as on its own. The calls in ForwardChecker meet many constraint classes in the suite, so the Java JIT compiler stops inlining them. The node count is fixed at 639,950, so I raised the test's time limit to 30 s.

The README reports these backtracking times as the best of several runs.

• A 100-Queens board takes about 15 ms and 185 search nodes.
• A 200-Queens board takes about 8 s and about 640,000 nodes.
• A hard Sudoku takes about 65 ms and about 8,700 nodes.

On the same search tree, the trail cut 100-Queens from 50 ms to 22 ms, and 200-Queens from 16.4 s to 8.1 s. The min-conflicts search places 1,000 queens in about 15 ms. The project has 61 tests, and one of them confirms that SEND + MORE = MONEY has exactly one solution, 9567 + 1085 = 10652.

My design notes list two known limits.

• MAC exists in the code, but the API can't select it. Exposing it would let me measure what AC-3 costs during search.
• Backtracking on N-Queens is sensitive to board size with the natural value order, and it stays fast up to about N = 150.

J'ai construit un solveur de problèmes de satisfaction de contraintes (CSP) en Java 21, et je l'ai exposé comme service REST Spring Boot. Un CSP a des variables, un ensemble de valeurs permises pour chacune, et des contraintes entre elles. J'ai écrit chaque algorithme moi-même, sans bibliothèque de CSP.

Le service résout les N-reines, le Sudoku, la coloration de graphes et des énigmes de chiffres comme SEND + MORE = MONEY. Une page du navigateur montre la recherche en direct par WebSocket.

Le backtracking est complet, donc il peut prouver qu'il n'existe aucune solution. Une recherche locale min-conflicts renonce à cette garantie, mais elle place 1 000 reines en 15 ms environ.

La recherche par backtracking assigne une variable à la fois, et elle annule tout choix qui mène à une impasse. Plusieurs techniques la rendent plus rapide.

• Le forward checking s'exécute après chaque assignation. Il retire les valeurs en conflit des variables voisines et s'arrête tôt quand l'une d'elles n'a plus de valeurs.
• AC-3 s'exécute une fois avant la recherche. Il rend chaque contrainte cohérente d'arc, ce qui veut dire que chaque valeur restante a une valeur compatible chez chaque voisin.
• MRV (minimum de valeurs restantes), l'ordre par défaut, choisit la variable qui a le moins de valeurs, et départage les égalités par le nombre de contraintes.
• Dom/WDeg divise le nombre de valeurs restantes par un nombre pondéré de contraintes. Une contrainte gagne du poids chaque fois qu'elle vide les valeurs d'une variable.
• Un DomainTrail enregistre les changements, donc une impasse ne restaure que les domaines BitSet qui ont changé.

Pour les N-reines avec N de 50 ou plus, l'API passe à min-conflicts. Elle part d'un placement glouton, puis déplace les reines en conflit vers leur colonne la moins en conflit jusqu'à ce qu'il n'y ait plus de conflit.

La vue en direct diffuse les événements de recherche par STOMP, un protocole de messages au-dessus de WebSocket. Les mises à jour du plateau sont limitées à environ 30 par seconde.

• J'ai remplacé les copies complètes des domaines par une trace. La première version copiait chaque domaine à chaque nœud de recherche, ce qui allouait de la mémoire proportionnelle à la taille du problème à chaque nœud. Mes notes de conception indiquent que la trace a rendu chaque nœud environ deux fois moins coûteux.
• Le forward checking est la propagation utilisée pendant la recherche, et AC-3 s'exécute seulement avant. Maintenir la cohérence d'arc à chaque nœud (MAC) retire plus de valeurs, mais relance AC-3 à chaque fois. Mes notes retiennent le forward checking avec un bon ordre des variables comme meilleur choix par défaut.
• L'API choisit une stratégie selon la taille du problème. Le backtracking reste le choix par défaut pour les petits plateaux, parce qu'il peut lister toutes les solutions. Min-conflicts s'occupe des grands N-reines, où le backtracking ralentit beaucoup.

Trois bogues échouaient en silence, et les tests ne les ont pas vus au début.

• Les sélecteurs de valeurs renvoyaient le domaine vivant. Le solveur réduisait ce domaine pendant qu'il explorait la première valeur, donc les choix restants pouvaient changer sous la boucle et la recherche devenait incomplète. Les sélecteurs parcourent maintenant une copie.
• Avec MAC, la propagation n'applique pas une contrainte qui n'expose aucun arc, c'est-à-dire aucune paire de variables qu'AC-3 peut vérifier. La somme d'une énigme de chiffres est une telle contrainte. Le solveur vérifie maintenant chaque contrainte sur chaque assignation complète.
• Dom/WDeg enregistrait un poids de 1,0 au premier échec, ce qui est le même que le poids par défaut. Le premier échec fait maintenant passer le poids à 2,0.

Le test des 200 reines tournait aussi environ deux fois plus lentement dans la suite complète que seul. Dans la suite, les appels de ForwardChecker rencontrent beaucoup de classes de contraintes, donc le compilateur JIT de Java arrête de les intégrer. Le nombre de nœuds est fixe à 639 950, donc j'ai porté la limite de temps du test à 30 s.

Le README donne ces temps de backtracking comme le meilleur de plusieurs exécutions.

• Un plateau de 100 reines prend environ 15 ms et 185 nœuds de recherche.
• Un plateau de 200 reines prend environ 8 s et environ 640 000 nœuds.
• Un Sudoku difficile prend environ 65 ms et environ 8 700 nœuds.

Sur le même arbre de recherche, la trace a fait passer les 100 reines de 50 ms à 22 ms, et les 200 reines de 16,4 s à 8,1 s. La recherche min-conflicts place 1 000 reines en 15 ms environ. Le projet a 61 tests, et l'un d'eux confirme que SEND + MORE = MONEY a exactement une solution, 9567 + 1085 = 10652.

Mes notes de conception listent deux limites connues.

• MAC existe dans le code, mais l'API ne permet pas de le choisir. L'exposer me permettrait de mesurer le coût d'AC-3 pendant la recherche.
• Le backtracking sur les N-reines est sensible à la taille du plateau avec l'ordre naturel des valeurs, et il reste rapide jusqu'à environ N = 150.