Heya, here's a crossword builder I am working on as a hobby project. Backend is pure Go, frontend is in Typescript. I have a personal backlog of features to add (like allowing users to create custom grids), and I'm glad to take any feedback on what I've got so far.
TL;DR: pick a grid, add some words, auto-fill, add some clues. Submit to NYT and make $$$ (good luck with that step though).
Haha, yep, indeed. I did try to bake in some throttling behavior up front, but just had to crank it up a bit now, will see how that holds. Oh yeah, and for the curious, I am running on E2 freebie in GCE, so my "scaling" limits are pretty pathetic.
This is very cool. I have a possible use case for this: spaced repetition for learning new vocabulary. If you could easily generate crosswords for the words someone is learning (plus some filler words that the learner already knows), it would be much more entertaining than reviewing Anki cards.
I think the constraints are more relaxed for this use case. The grid really doesn't need to look as neat as an NYT crossword puzzle.
I bet you can already market this to ESL teachers, and perhaps make some $$$ off your hobby project. Good luck with that! (Of course, I mean it sincerely, not ironically :-))
Thanks! It's a cool idea and giving a user the ability to specify the words, but let the algo choose their locations might be an easy extension to try out. The behavior you describe can then be met. I've added it to my personal backlog, cheers!
BTW, grid neatness isn't a limitation itself, the size and complexity (overlaps, large words) are. Also I already do symmetry checks, so helping users generate symmetric grids shouldn't be too hard.
Mulling over it. I feel the underlying solver itself is something I've invested a fair bit of time and I'm not sure I want to open source it yet. I might marinate on it a bit and do it in the future.
As someone who frequently does the full and mini NYT crosswords, I really like this idea. I’ve wondered what it’d be like trying to make my own. This seems like a useful tool for giving it a try.
Some feedback:
- The chart showing the distribution of word length is very cool.
- Maybe you could educate newbies about how can choose a grid. I’m wondering if the predefined ones you provide are commonly seen in NYT. Does NYT prefer certain grids? Are you more likely to be accepted by NYT with a unique grid?
- Custom grids sounds like a great feature. I’m guessing there are some rules about symmetry and no two-letter words that you can help users with.
- Auto filling on an empty grid basically does all the work except clue writing? Maybe that’s intensive for your back-end? I noticed the page hang when submitting that. Maybe you can require some percentage for the user to first fill in on their own? As a user I think I’d only want the grid to highlight areas where I have an invalid word.
> I’m guessing there are some rules about symmetry and no two-letter words that you can help users with.
Yes, and figuring out how to do the validation in a sensible way is probably my next step. I already have the encoding figured out, in fact if you examine the HTML you can see the grids as b64 binary strings, so the next step is the UX.
> Auto filling on an empty grid basically does all the work except clue writing
Sort of, having looked at a few other places that do this type of thing seriously there are other things about construction I'm not doing yet, like avoiding "CAT" and "CATS" or other substrings in general, and scoring words. I support the latter, but not on my poor E2 GCE instance (need more RAM). Clues aren't a problem I'm ready to solve yet, so I just cross-ref a nice site that has some of the historical ideas.
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/), 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?
[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)
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.
16 comments
[ 4.8 ms ] story [ 56.1 ms ] threadTL;DR: pick a grid, add some words, auto-fill, add some clues. Submit to NYT and make $$$ (good luck with that step though).
Thanks for the traffic, I mean, the love, y'all!
I think the constraints are more relaxed for this use case. The grid really doesn't need to look as neat as an NYT crossword puzzle.
I bet you can already market this to ESL teachers, and perhaps make some $$$ off your hobby project. Good luck with that! (Of course, I mean it sincerely, not ironically :-))
BTW, grid neatness isn't a limitation itself, the size and complexity (overlaps, large words) are. Also I already do symmetry checks, so helping users generate symmetric grids shouldn't be too hard.
Some feedback: - The chart showing the distribution of word length is very cool. - Maybe you could educate newbies about how can choose a grid. I’m wondering if the predefined ones you provide are commonly seen in NYT. Does NYT prefer certain grids? Are you more likely to be accepted by NYT with a unique grid? - Custom grids sounds like a great feature. I’m guessing there are some rules about symmetry and no two-letter words that you can help users with. - Auto filling on an empty grid basically does all the work except clue writing? Maybe that’s intensive for your back-end? I noticed the page hang when submitting that. Maybe you can require some percentage for the user to first fill in on their own? As a user I think I’d only want the grid to highlight areas where I have an invalid word.
> I’m guessing there are some rules about symmetry and no two-letter words that you can help users with.
Yes, and figuring out how to do the validation in a sensible way is probably my next step. I already have the encoding figured out, in fact if you examine the HTML you can see the grids as b64 binary strings, so the next step is the UX.
> Auto filling on an empty grid basically does all the work except clue writing
Sort of, having looked at a few other places that do this type of thing seriously there are other things about construction I'm not doing yet, like avoiding "CAT" and "CATS" or other substrings in general, and scoring words. I support the latter, but not on my poor E2 GCE instance (need more RAM). Clues aren't a problem I'm ready to solve yet, so I just cross-ref a nice site that has some of the historical ideas.
> I noticed the page hang when submitting that.
Yep, getting hugged to death :)
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/), 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?
[1] https://dawnofthe.dad/
[2] https://web.stanford.edu/~jduchi/projects/crossword_writeup....
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.