5 ms·

Solving a wooden puzzle using Haskell

69 points by Bogdanp 1y ago

fjfaase 1y ago
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]
asplake 1y ago
I missed any link to the puzzle itself. Does anyone here know where you might get one from?
- _ache_ 1y ago
  Here is the one from the article. https://linsoluble-casse-tete.fr/products/25-y-constantin https://linsoluble-casse-tete.fr/products/25-y-constantin
kqr 1y ago
I have a 2D variant of this puzzle and got curious about the solvability of various starting positions so I made this graphical tool: https://xkqr.org/info/tetrispuzzlesolver.html https://xkqr.org/info/tetrispuzzlesolver.html Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle.
_ache_ 1y ago
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. https://ache.one/polycube.cpp https://ache.one/polycube.cpp
- gerdesj 1y ago
  Good job. When you said "in French" ... well, "IS_VALIDE" is quite something to see! It seems you are fluent in Franglais - https://en.wikipedia.org/wiki/Franglais https://en.wikipedia.org/wiki/Franglais. I have only respect for someone who can flit between languages with that facility.
  - _ache_ 1y ago
    OMG. I was quite young. /o\ I wish it was code-switching but the true may be that my english wasn't very good. I learn yesterday that a French spy DGSE (French NSA) was spotted by the Canadian after exactly this kind of english errors (and other hints like the use of "octet" instead of "byte" and compiled with french local).
    - gerdesj 1y ago
      An octet is a byte but I get the point - it's when you use a word in context. I find it fascinating how you slam words together - who cares about "correct"? Is there really a correct way to program in C++, in both French and a nod to English? In the end if it compiles and works - who cares! Viva la Franglais++
      - defrost 1y ago
        An octet is a a musical composition for eight instruments or voices, Or it's a set of 8 things (such as 8 bits) .. a byte is the smallest addressable unit of storage, frequently but not always 8 bits (hence the need for CHAR_BIT), it's tied to hardware; TI DSP chips can have 32 bit or 64 bit bytes.
cocoto 1y ago
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.
- cocoto 1y ago
  Edit: Under 10s with CP-SAT after removing many variables (had multiple variables for the same pieces).
crdrost 1y ago
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: orientations = concat [ [ [(0,0,0), (t,0,0), (2*t,0,0), (3*t,0,0), (2*t, a, b)], [(0,0,0), (0,t,0), (0,2*t,0), (0,3*t,0), (a,2*t,b)], [(0,0,0), (0,0,t), (0,0,2*t), (0,0,3*t), (a,b,2*t)] ] | (a, b) <- [(1,0), (-1, 0), (0, 1), (0, -1)], t <- [1, -1]] 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.
- fn-mote 1y ago
  I am betting that the author came up with the filtering method in 5 minutes or less and quickly got it working. The 10 paragraph blog post is the “hard” part: explaining to others who don’t have the same base knowledge. If I read it correctly, they do even less human-powered work than your solution. It just looks hard because the machinery is unfamiliar.
mkl 1y ago
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.
dividuum 1y ago
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 :-)
ustad 1y ago
You all might like the 3x3x3 Soma Cube: https://en.m.wikipedia.org/wiki/Soma_cube https://en.m.wikipedia.org/wiki/Soma_cube
lordgrenville 1y ago
I think in English one would usually say "position" where the author uses "disposition". (Disposition is closer to "temperament"/"personality".)
deleted 1y ago
[deleted]
justinsimporios 1y ago
[flagged]
mdrslmr 1y ago
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.
- mdrslmr 1y ago
  With some "random" changes the time for computation on my computer went down from 1534s to 67s. What I did is exclude some pieces I found suspicious. Therefore I introduced basically the function exclude and had to do some bookkeeping of already places pieces. ```haskell len :: V3 Int -> Float len (V3 x y z) = sqrt (x'*x' + y'*y' + z'*z') where x' = fromIntegral x :: Float y' = fromIntegral y :: Float z' = fromIntegral z :: Float exclude :: Shape -> Shape -> Bool exclude [a1, _, _, d1, _] [a2, _, _, d2, _] = len (a2 - a1) < 1.1 && len (d2 - d1) < 1.1 ``` ```haskell conflict :: Shape -> Shape -> [Shape] -> Bool conflict occs piece oldPieces = any (\voxel -> elem voxel piece) occs || any (\o -> exclude o piece) oldPieces ``` ```haskell subsolutionsSmart :: Int -- ^ How many pieces should be in the subsolution we're looking for? -> Shape -- ^ Unavailable voxels, already occupied by some piece -> [Shape] -> [[Shape]] subsolutionsSmart 0 _ _ = [[]] subsolutionsSmart n occupiedVoxels oldPieces = do let freeVoxel = pickFreeVoxel occupiedVoxels newPiece <- filter (\piece -> elem freeVoxel piece && not (conflict occupiedVoxels piece oldPieces) ) allValidPieces let updatedOccupiedVoxels = newPiece <> occupiedVoxels let updatedOldPieces = (newPiece:oldPieces) otherPieces <- subsolutionsSmart (n - 1) updatedOccupiedVoxels updatedOldPieces return $ newPiece : otherPieces ``` ```haskell allSolutionsSmart :: [[Shape]] allSolutionsSmart = subsolutionsSmart 25 [] [] ```
concavebinator 1y ago
Reminds me of a 2D puzzle I solved using Haskell https://github.com/concavegit/tile-placement-puzzle https://github.com/concavegit/tile-placement-puzzle 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

69 points by Bogdanp 1y ago

fjfaase 1y ago

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]

asplake 1y ago

I missed any link to the puzzle itself. Does anyone here know where you might get one from?

_ache_ 1y ago
Here is the one from the article. https://linsoluble-casse-tete.fr/products/25-y-constantin https://linsoluble-casse-tete.fr/products/25-y-constantin

kqr 1y ago

I have a 2D variant of this puzzle and got curious about the solvability of various starting positions so I made this graphical tool: https://xkqr.org/info/tetrispuzzlesolver.html https://xkqr.org/info/tetrispuzzlesolver.html Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle.

_ache_ 1y ago

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. https://ache.one/polycube.cpp https://ache.one/polycube.cpp

gerdesj 1y ago
Good job. When you said "in French" ... well, "IS_VALIDE" is quite something to see! It seems you are fluent in Franglais - https://en.wikipedia.org/wiki/Franglais https://en.wikipedia.org/wiki/Franglais. I have only respect for someone who can flit between languages with that facility.
- _ache_ 1y ago
  OMG. I was quite young. /o\ I wish it was code-switching but the true may be that my english wasn't very good. I learn yesterday that a French spy DGSE (French NSA) was spotted by the Canadian after exactly this kind of english errors (and other hints like the use of "octet" instead of "byte" and compiled with french local).
  - gerdesj 1y ago
    An octet is a byte but I get the point - it's when you use a word in context. I find it fascinating how you slam words together - who cares about "correct"? Is there really a correct way to program in C++, in both French and a nod to English? In the end if it compiles and works - who cares! Viva la Franglais++
    - defrost 1y ago
      An octet is a a musical composition for eight instruments or voices, Or it's a set of 8 things (such as 8 bits) .. a byte is the smallest addressable unit of storage, frequently but not always 8 bits (hence the need for CHAR_BIT), it's tied to hardware; TI DSP chips can have 32 bit or 64 bit bytes.

cocoto 1y ago

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.

cocoto 1y ago
Edit: Under 10s with CP-SAT after removing many variables (had multiple variables for the same pieces).

crdrost 1y ago

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: orientations = concat [ [ [(0,0,0), (t,0,0), (2*t,0,0), (3*t,0,0), (2*t, a, b)], [(0,0,0), (0,t,0), (0,2*t,0), (0,3*t,0), (a,2*t,b)], [(0,0,0), (0,0,t), (0,0,2*t), (0,0,3*t), (a,b,2*t)] ] | (a, b) <- [(1,0), (-1, 0), (0, 1), (0, -1)], t <- [1, -1]] 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.

fn-mote 1y ago
I am betting that the author came up with the filtering method in 5 minutes or less and quickly got it working. The 10 paragraph blog post is the “hard” part: explaining to others who don’t have the same base knowledge. If I read it correctly, they do even less human-powered work than your solution. It just looks hard because the machinery is unfamiliar.

mkl 1y ago

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.

dividuum 1y ago

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 :-)

ustad 1y ago

You all might like the 3x3x3 Soma Cube: https://en.m.wikipedia.org/wiki/Soma_cube https://en.m.wikipedia.org/wiki/Soma_cube

lordgrenville 1y ago

I think in English one would usually say "position" where the author uses "disposition". (Disposition is closer to "temperament"/"personality".)

deleted 1y ago

[deleted]

justinsimporios 1y ago

[flagged]

mdrslmr 1y ago

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.

mdrslmr 1y ago
With some "random" changes the time for computation on my computer went down from 1534s to 67s. What I did is exclude some pieces I found suspicious. Therefore I introduced basically the function exclude and had to do some bookkeeping of already places pieces. ```haskell len :: V3 Int -> Float len (V3 x y z) = sqrt (x'*x' + y'*y' + z'*z') where x' = fromIntegral x :: Float y' = fromIntegral y :: Float z' = fromIntegral z :: Float exclude :: Shape -> Shape -> Bool exclude [a1, _, _, d1, _] [a2, _, _, d2, _] = len (a2 - a1) < 1.1 && len (d2 - d1) < 1.1 ``` ```haskell conflict :: Shape -> Shape -> [Shape] -> Bool conflict occs piece oldPieces = any (\voxel -> elem voxel piece) occs || any (\o -> exclude o piece) oldPieces ``` ```haskell subsolutionsSmart :: Int -- ^ How many pieces should be in the subsolution we're looking for? -> Shape -- ^ Unavailable voxels, already occupied by some piece -> [Shape] -> [[Shape]] subsolutionsSmart 0 _ _ = [[]] subsolutionsSmart n occupiedVoxels oldPieces = do let freeVoxel = pickFreeVoxel occupiedVoxels newPiece <- filter (\piece -> elem freeVoxel piece && not (conflict occupiedVoxels piece oldPieces) ) allValidPieces let updatedOccupiedVoxels = newPiece <> occupiedVoxels let updatedOldPieces = (newPiece:oldPieces) otherPieces <- subsolutionsSmart (n - 1) updatedOccupiedVoxels updatedOldPieces return $ newPiece : otherPieces ``` ```haskell allSolutionsSmart :: [[Shape]] allSolutionsSmart = subsolutionsSmart 25 [] [] ```

concavebinator 1y ago

Reminds me of a 2D puzzle I solved using Haskell https://github.com/concavegit/tile-placement-puzzle https://github.com/concavegit/tile-placement-puzzle 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