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.
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.
I did the exact same thing in C++ 10 years ago ! Same puzzle. :D
I wonder if I can still find the source code. (Found it! Source code was in French and not very elegant but it works, glorified brute force aka Backtracking).
I'm eager to improve it to find ALL solutions, not just the first one.
I tried modeling the problem as a mixed-integer linear program (one binary variable for each possible piece position) and CP-SAT solved this one in two minutes.
I'm really surprised at the whole filtering the rotation matrices thing, to me it is like, the long side of the piece is an arrow, that arrow can be pointed in one of six directions, I can rotate in one of four directions after that, so there's 24 orientations:
With translations, okay, there's 40 of those per piece and figuring out the right direction to go with those requires a cross product, sure, let's just generate 5×5×5 = 125 of them and filter out the right 40. But doing 20,000 determinants and whatever it was, 10-15 paragraphs, to filter out the right 24 orientations doesn't make as much sense to me.
My parents have a similar 3×3×3 puzzle, that they couldn't remember how to solve, so most times someone visited them and had a go at it, the puzzle would be left in pieces until I next visited and put it back together. One Christmas I wrote a similar solver in Python and found there were 16 solutions, only a few of which I had found (though most I had seen only once). I printed out diagrams for each solution made with Matplotlib, so now the puzzle can always be put back together. My grandmother had a different 3×3×3 one that turned out to have something like 100-200 solutions.
I wrote a solver for a similar puzzle: IIRC it was 3x3x3 with different shaped pieces that left some space unfilled. Some of the pieces had holes and you additionally had three 3-long metal rods to place inside somewhere. I ran my code and it didn’t find a solution. Best it could do was fit all wooden pieces and two of those rods through holes inside the pieces. [Spoiler] Turns out, the solution was to ignore to rods first, leave a 3x1x1 “tunnel” and put all three rods in there, completely ignoring the holes in the wooden pieces. I remember being slightly annoyed :-)
My "conjecture" is, that some depositions could be excluded by comparing two shapes: e.g. if they are back to back, side by side, nob on nob. Here I have in mind two shapes where one is just a rotation around the long axis of the other and shifted by only one unit perpendicular to the axis of rotation.
IIRC it kept a list of board states, updated the list of board states by taking each one and applying possible moves, then removed congruencies or any state that did not have a valid next move.
The pattern seems similar to your approach that deals with rotations, though in 3D
18 comments
[ 2.8 ms ] story [ 37.7 ms ] thread[1]: https://arxiv.org/abs/cs/0011047
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...
Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle.
I wonder if I can still find the source code. (Found it! Source code was in French and not very elegant but it works, glorified brute force aka Backtracking).
I'm eager to improve it to find ALL solutions, not just the first one.
https://ache.one/polycube.cpp
IIRC it kept a list of board states, updated the list of board states by taking each one and applying possible moves, then removed congruencies or any state that did not have a valid next move.
The pattern seems similar to your approach that deals with rotations, though in 3D