In CSPs, each cell is a 'decision variable' with a 'domain' of values, which get pruned by 'constraints' that propagate to values invalidated by the decisions made in the connected variables, until the whole 'problem' gets into either a solution which 'satisfies' all the constraints, or a contradictory state where a variable's domain is empty, causing the algorithm to backtrack.
CSPs have the advantage of having clear and efficient methods to go back to a previous state and keep exploring every alternate possibility, rather than having to restart from the beginning. The article hints at that possibility ('saving checkpoints' or'reverse the collapsing of a cell'); there's a whole field of study dedicated on the best ways to do that on a large scale for very general problems.
Personally, I find CSPs overly general and mired in esoteric, byzantine terminology. It's a large cognitive load to put on people to run through the glossary of terms just to talk about the problem set up. I don't think the quantum mechanic analogy is great but I can see it being much more intuitive than the obscure language of CSPs.
[0] https://www.boristhebrave.com/2021/10/31/constraint-based-ti...
Of course terminology for CSPs will get confusing when you get to represent them mathematically; but that happens to anything that you turn into math. The core concept is quite familiar and intuitive.
Max Gumin focused on just the constraint solver and added a "minimum entropy heuristic", popularized the work and coined the term "wave function collapse", as the way the solver worked was evocative of (a naive view) of how quantum mechanics solves systems [2]. Gumin's repo also has many other resources of implementations and descriptions [3].
I've published a paper on an extension that adds in a type of backtracking to both the "WFC" portion of the solver and the modify in blocks portion of the solver, which can be found in [4], for those interested.
[0] https://paulmerrell.org/model-synthesis/
[1] https://www.boristhebrave.com/2021/10/26/model-synthesis-and...
[2] https://github.com/mxgmn/WaveFunctionCollapse
[3] https://github.com/mxgmn/WaveFunctionCollapse?tab=readme-ov-...
Another, where you can set cells and then have it solve: https://oskarstalberg.com/game/wave/wave.html
And an itch.io game where you are the wave function selector: https://bolddunkley.itch.io/wfc-mixed
I thought this concept would have found more traction in the world of procgen (in games), because it's pretty neat. But I found it difficult to work with, so perhaps others also did!
This is in contrast to LLMs, and I assume it comes from that it discards improbable things instead of choosing probable things.
Nicely fitting for the (sort of) physical quantum wave function collapse behavior.
leetrout•4mo ago