Hi HN; Author here of the article;
I spent 9 months working on a problem I wasn’t sure could be solved at the start; creating a scalable deterministic freeform crossword generating algorithm with sufficient connectivity/density.
In January I had a breakthrough that made this possible and also made the algorithm scalable. The insight was a single-line pruning rule that collapses branching factor, tail formation and path redundancy, further described in the article.
I wasn’t happy yet, because I couldn’t create clustered crosswords. I spent a long time hacking on that issue and came up with a solution for that, making it possible to exactly recreate NYT-style crossword layouts just from their word list.
Pushing this to the limits on my laptop, I managed to squeeze out a nearly 5000-word crossword with over 10k intersections and a grid filling of 54% letters against 46% whitespace, which ran overnight using up all my laptops’ resources.
Finally I built a web app around it for anyone to use for free, and I’d love for you to try it out and hear your feedback or answer questions. Remember that the app runs against modest hardware and there is a single queue. You can find it here: https://clueless.crossword.is
A formal technical writeup will follow together with the release of the source code, but this takes longer than planned. In the meantime I’d be happy to discuss about the project and the algorithm.
Hi HN; Author here of the article; I spent 9 months working on a problem I wasn’t sure could be solved at the start; creating a scalable deterministic freeform crossword generating algorithm with sufficient connectivity/density.
In January I had a breakthrough that made this possible and also made the algorithm scalable. The insight was a single-line pruning rule that collapses branching factor, tail formation and path redundancy, further described in the article.
I wasn’t happy yet, because I couldn’t create clustered crosswords. I spent a long time hacking on that issue and came up with a solution for that, making it possible to exactly recreate NYT-style crossword layouts just from their word list.
Pushing this to the limits on my laptop, I managed to squeeze out a nearly 5000-word crossword with over 10k intersections and a grid filling of 54% letters against 46% whitespace, which ran overnight using up all my laptops’ resources.
Finally I built a web app around it for anyone to use for free, and I’d love for you to try it out and hear your feedback or answer questions. Remember that the app runs against modest hardware and there is a single queue. You can find it here: https://clueless.crossword.is
A formal technical writeup will follow together with the release of the source code, but this takes longer than planned. In the meantime I’d be happy to discuss about the project and the algorithm.
Hope you find it interesting!