search

szunami / xwords-rs

Tools to fill crosswords
Apache License 2.0
7 stars 1 forks source link

Could be sped up dramatically with better state-space search #131

Open BartMassey opened 3 years ago

BartMassey commented 3 years ago

There are a number of algorithmic tricks to make the state-space search dramatically faster, for example variable ordering, value-ordering, forward-pruning, backjumping, LDS/DDS. Here's a paper by my PhD advisor Matt Ginsberg describing Dr Fill, which is probably currently the world's fastest crossword-filler. A Rust implementation of the solver described here would be a really interesting project.

szunami commented 3 years ago

After reviewing the paper, I think there are a ton of useful implementation details to be mined.

Right now the word list I have cobbled together includes a lot of poor fill; improving the quality of fill would involve either removing crummy words, or adding some concept of a "fill score" to words based on how legit they are. Both of these processes have broad implications for the perf of xwords, and I suspect that if I go down that direction, I might need some algorithmic enhancements to keep things in real time.

Thanks again for the link!