Hacker News Reader

Solving this kind of puzzles is equal to solving an exact cover. Exact cover is known to be NP-complete.

Indeed it is, and Donald Knuth spends a substantial part of the latest volume (4B) of The Art of Computer Programming on solving exact cover problems like this using Dancing Links! He presented an earlier version of the algorithm in this legendary article [1], but as good as that article is, the book is even better (and the algorithm improved!). It also has tons of exercises like this. Cannot recommend it highly enough.

[1]: https://arxiv.org/abs/cs/0011047

Yes that's a brilliant article. I do not think it is in the book yet?

I used a poor man's version to solve a puzzle where one arranges polymino pieces on a grid spelling out the date [1]. No pointers, just keeping track of deleted rows and columns in the recursion.

It is not at all obvious that all 366 days can be solved. To my dismay all of them can be solved in multiple ways - as a human I find some days quite tricky.

[1] https://metterklume.github.io/puzzle/2024/12/24/calendar-puz...

It is in the book, it’s a big part of 4B, which was published in 2022. The main topics are backtracking, exact cover using Dancing Links and satisfiability. It’s my favorite volume of the whole bunch.

Reply on news.ycombinator.com