userundefined's comments

Been working on a Google-sheet backed workout tracker, which basically makes it easy for me to see what I've done or not done recently and pick the next thing to do. I'm thinking of open sourcing this soon, but need to do some "de-monolithing" first.

This is definitely not the fastest sudoku solver out there, but the visualizations tend to be fun to watch and should give you an idea of how search incrementally builds up the solution, eliminates uninteresting parts, backtracks on failure, and how the various parameters affect its behavior. You can expand the "?" to see the FAQ about what the colors represent and a bit more details on the parameters.

I also have a bunch of the technical details about how this all comes together in my blog (e.g., this post gives an overview: https://blog.dawnofthe.dad/posts/solver-basics/), and if you want to see another application of this same solver, check out the crossword builder on the same site. The model for crosswords is of course very different, but the underlying engine is the same. The only thing that crosswords share with sudoku is one all-different constraint: while sudokus are basically just one giant glob of all-different constraints, the crossword only has the one, to ensure no word is used twice. This all-different constraint is the "Sparse" one (in the UX), and being tailored for the crossword use-case, unsurprisingly tends to perform poorly for sudokus (because while it's very fast, it's also very simple).

In any event, it's been a fun project to nerd out on, and I hope you enjoy poking at it. I'll be happy to take any questions about it.

Curious to hear if others had a similar experience, or if I'm just rediscovering/parroting a well-known technique and don't know its name. Closest I could dig up was "The Feynman Technique", which is a bit more elaborate than what I have in mind.

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.

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.

> 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 :)

Thanks for the traffic, I mean, the love, y'all!

TL;DR: pick a grid, add some words, auto-fill, add some clues. Submit to NYT and make $$$ (good luck with that step though).