[1] suggests it uses a Constraint Satisfaction Problem solver and according to the network tab of my browser the solver seems to run on the server (the data is exchanged over a WebSocket connection). I'm wondering what kind of algorithm the solver uses too, and if it relies on any heuristics or specific data structures for this problem. For example [2] shows best results using bitarrays and a mix of "forward checking", "conflict directed backjumping" and "dynamic variable ordering". (which are fancy terms to describe the methods one usually comes up with to solve a Sudoku grid)[1] https://dawnofthe.dad/
[2] https://web.stanford.edu/~jduchi/projects/crossword_writeup....
userundefined|2 years ago
In a bit more detail, the CSP solver does indeed apply forward checking, and a fancier version of that, arc consistency, is available too, but ends up being slower on the whole. There's dynamic variable ordering (i.e., "Which word to try next") and conflict directed backjumping (i.e., "Solver's stuck, how far to go back?"). There's some relatively memory hungry structures for checking word constraints, e.g., when two words overlap and one is assigned we want to remove impossible values for the other word, and a specialized "sparse all different" constraint that disallows using a given word more than once.
And also yes, all this happens on the backend and websockets are used to send the latest state to the client.