| ▲ | Solving a wooden puzzle using Haskell(glocq.github.io) |
| 69 points by Bogdanp 6 days ago | 32 comments |
| |
|
| ▲ | crdrost 3 days ago | parent | next [-] |
| 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 3 days ago | parent [-] | | 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. |
|
|
| ▲ | _ache_ 3 days ago | parent | prev | next [-] |
| 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 |
| |
| ▲ | gerdesj 3 days ago | parent [-] | | 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. I have only respect for someone who can flit between languages with that facility. | | |
| ▲ | _ache_ 3 days ago | parent [-] | | 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 3 days ago | parent [-] | | 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 3 days ago | parent | next [-] | | 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. | | |
| ▲ | gerdesj 3 days ago | parent [-] | | There are times when an exhaustive and formal definition of a word is not required. This is one of them. However, I am aware that for some people, it can be annoying when someone else (me in this case) is seemingly lazy or just plain wrong when deploying words. I used to be somewhat unkind about grammatical errors but let's face it: grammar is what the majority of people say it is and not what is pinned down in a book half-read and quarter-remembered from years ago. A bit is perhaps the smallest addressable unit of storage (says my light switch) A byte manages to convey 256 different states and I would need eight light switches to store them. | | |
| ▲ | defrost 3 days ago | parent [-] | | I'm largely indifferent to errors in spelling, grammar, or definition, save for those cases where others are incorrectly correcting others. The definition of byte is not a matter of grammar, and here on a forum centered about computing technology and business the distinction that matters not to you matters to many - CHAR_BIT is still part of current standards in important languages and hardware w/out 8-bit bytes is still in current use. |
|
| |
| ▲ | rkomorn 3 days ago | parent | prev [-] | | > Viva la Franglais++ It's "vive", not "viva", in French, and "français" and "anglais" are both masculine, so "franglais" is masculine as well (so it would use "le" as an article). | | |
| ▲ | xdfgh1112 2 days ago | parent [-] | | Way to miss the point. | | |
| ▲ | rkomorn 2 days ago | parent [-] | | Nah. It's a pet peeve from years of hearing "viva la France!" from various Americans. | | |
| ▲ | gerdesj 2 days ago | parent [-] | | I'm not American and I really do know what I'm doing when I'm taking le pise. You'll probably be more likely to hear "viva los Frenchies" from Brits confusing Spanish with French. To us Germanics, you Romantics sound all the same ... or something 8) |
|
|
|
|
|
|
|
|
| ▲ | concavebinator a day ago | parent | prev | next [-] |
| Reminds me of a 2D puzzle I solved using Haskell 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 |
|
| ▲ | fjfaase 6 days ago | parent | prev | next [-] |
| Solving this kind of puzzles is equal to solving an exact cover. Exact cover is known to be NP-complete. |
| |
| ▲ | OskarS 3 days ago | parent | next [-] | | 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 | | |
| ▲ | tirutiru 2 days ago | parent [-] | | 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... | | |
| ▲ | OskarS 2 days ago | parent [-] | | 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. |
|
| |
| ▲ | 3 days ago | parent | prev [-] | | [deleted] |
|
|
| ▲ | dividuum 3 days ago | parent | prev | next [-] |
| 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 :-) |
|
| ▲ | kqr 3 days ago | parent | prev | next [-] |
| 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 Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle. |
|
| ▲ | mdrslmr a day ago | parent | prev | next [-] |
| 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 19 hours ago | parent [-] | | 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 [] []
```
|
|
|
| ▲ | mkl 3 days ago | parent | prev | next [-] |
| 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. |
|
| ▲ | lordgrenville 2 days ago | parent | prev | next [-] |
| I think in English one would usually say "position" where the author uses "disposition". (Disposition is closer to "temperament"/"personality".) |
|
| ▲ | ustad 2 days ago | parent | prev | next [-] |
| You all might like the 3x3x3 Soma Cube:
https://en.m.wikipedia.org/wiki/Soma_cube |
|
| ▲ | cocoto 3 days ago | parent | prev | next [-] |
| 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 2 days ago | parent [-] | | Edit: Under 10s with CP-SAT after removing many variables (had multiple variables for the same pieces). |
|
|
| ▲ | asplake 3 days ago | parent | prev | next [-] |
| I missed any link to the puzzle itself. Does anyone here know where you might get one from? |
| |
|
| ▲ | 2 days ago | parent | prev | next [-] |
| [deleted] |
|
| ▲ | justinsimporios 2 days ago | parent | prev [-] |
| [flagged] |
