5 ms·

Very cool! The speed at which it auto-fills a grid is mesmerizing. Is this done server-side or client-side? I sometimes build crosswords for fun, and I have tr

by gaazoh 3y ago

Very cool! The speed at which it auto-fills a grid is mesmerizing. Is this done server-side or client-side? I sometimes build crosswords for fun, and I have tried some native building apps, but I didn't find one that's good for building French rule crosswords. The best I have so far is [this one](https://casevide.fr/creation/outil/ https://casevide.fr/creation/outil/), that's basically just a dictionary lookup and it's very slow (pure client-side JS), but still allowed me to build a handful of puzzles. How hard do you reckon would it be to adapt your solver to work with French rules (no symmetry, 2-letter words allowed, minimizing black squares)? Or any other crossword style (French "arrow-words", British cryptic crosswords, Italian puzzles with no black squares but delimiters between squares...)? Maybe I'll give it a try myself. What resources did you use for figuring out the algorithm? Is your source code available?

nbe 3y ago
[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/ https://dawnofthe.dad/ [2] https://web.stanford.edu/~jduchi/projects/crossword_writeup.pdf https://web.stanford.edu/~jduchi/projects/crossword_writeup....
- userundefined 3y ago
  This is pretty much spot on. 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.

by gaazoh 3y ago

nbe 3y ago

[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/ https://dawnofthe.dad/ [2] https://web.stanford.edu/~jduchi/projects/crossword_writeup.pdf https://web.stanford.edu/~jduchi/projects/crossword_writeup....

userundefined 3y ago
This is pretty much spot on. 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.