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.
I'm still working on and off on my https://dawnofthe.dad/crossword, albeit most of the guts (solver backing the crossword builder) have been stable and lately most of the work has been on the front-end. On that note, I've been meaning to rewrite the UX component to be HTML element based, rather than canvas.
I've got a CSP solver powering things like a sudoku solver and a crossword builder on my site (https://dawnofthe.dad/). Recently I've been playing with NxN sudokus and created https://dawnofthe.dad/ndoku to try out a few algorithms/implementations of the all-different constraint, which is at the heart of sudokus. To expand on that, I decided to evaluate the performance of the various implementations of the all-different constraint in a somewhat more rigorous fashion, and this is what this article is about.
I've built a site that lets you play around with solving NxN sudokus, up to 36x36, backed by a Constraint Satisfaction Problem (CSP) solver. The site exposes a bunch of parameters that influence how this problem is solved, including how the cells are selected, what values are attempted first, how the problem is modeled, and how quickly the solver attempts to eliminate impossible states after each run. Each of these comes with a set of trade-offs, like a more thorough elimination algorithm takes longer to run between each step, so each step takes longer, and it can be interesting to try out different combinations to see which result in fasted solutions, fewest backtracks, and so on.
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.
I've started writing a blog for a crossword builder / sudoku solver site (https://dawnofthe.dad) and in the process of doing so found a few ways of improving the site/functionality itself. This made me think back to the rubber duck technique, but instead applied as a means for improvement, rather than just debugging. So I wrote up a short post about that, and that's what this is.
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.
> 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.
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).
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.
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.
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.