Dennis made this puzzle. It got taken apart a while back and I never mustered the drive to put it back together, but now I want to send it to my niece, so I really should put it together so she knows it can be solved. I don't know how long solving it by hand would take, but it should be a simple matter to write a computer program to solve it, and it was. Took me a few hours over the last couple of days.
In a single plane:
- A piece can rotated to any of 4 orientations.
- A piece can be flipped upside down, so there are 2 situations.
A piece can be in any of the 4 planes.
The cube can be sliced into four planes and this can be done 3 ways:
- horizontally
- vertically
- orthogonal to the other two
Multiply those together (4 x 2 x 4 x 3) and we have 96 possibilities.
In a single plane, using a single orientation, just sliding the piece around in the 4 x 4 space:
- A 2 x 4 piece can have 3 positions.
- A 3 x 3 piece can have 4 positions.
In sum:
- The (5) 2 x 2 pieces have 3 x 96 possible positions.
- The (5) 3 x 3 pieces have 4 x 96 possible positions.
Combining all these we have (3*96)^5 x (4*96)^5 or 1.6543163e+25.
I think. I may have it all backwards.
If that is the correct value, it is doubtful whether a brute force program will be able to solve the puzzle. I'm guesstimating it will take a billion years. On the other hand, many possibilities will fail almost immediately. At this point I was wondering whether it is worth going ahead with writing the program.
The lure of solving an unsolvable problem was too great and I went ahead with the program. It only took a few hours over a couple of days to write and after 7 or 8 minutes of execution time, it came up with a solution that actually worked.
With some embellishments, I was able to have it run through all the possible permutations and it delivered an even dozen solutions. It only took 42 minutes to deliver these answers, not a billion years, so something is not right.
Faced with this dilemma, I find it sometimes helps to explain the situation in English, so here is an exposition of the mechanics of the program. Hopefully, it is not too technical.
The cube is 4 units on a side, so there are 64 (4 x 4 x 4) positions. Each position is represented by a bit in 64-bit computer word. A single piece's position in the cube is represented by setting the appropriate bits in a word. A set of nested loops iterates through all the possible permutations (enumerated above) and a set of procedures translates the pattern of the piece in question into it's location in the cube.
We start by generating a word for each possible position for each piece. This doesn't take long, less than a millisecond, as there are only 672 of these ((4 x 96) + (3 x 96)). Each of these words is treated as a bit mask. If you AND two of these together and the result is zero, then there is no interference, so those two pieces, in those positions may coexist in the cube. If the result is not zero, then the pieces interfere with each other and this combination cannot be part of the solution.
If the result is zero, then these two masks can be OR'd together to give us a new mask. We can then proceed to the next piece and iterate through all the masks until we find one that does not interfere. If we cannot find such a piece, we go back to the previous piece and try the next position.
Now it could be that many of the positions are excluded early on, so that we only end up actually having to test a small fraction of the possible combinations. Still, it makes me wonder if I am missing something fundamental. Sometimes Lady Luck does shine on us, but this doesn't seem like this is one of those situations. I spent some time working on program to solve the Eternity II Puzzle, and that kind of persuaded me of the futility of applying brute force tactics against insurmountable odds.
Source code here.
No comments:
Post a Comment