3 ms·

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

• OskarS 1y ago
  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 https://arxiv.org/abs/cs/0011047
  • tirutiru 1y ago
    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-puzzle.html https://metterklume.github.io/puzzle/2024/12/24/calendar-puz...
    • OskarS 1y ago
      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.
• deleted 1y ago
  [deleted]