Cube Puzzle Solver Port-Mortem

Number of times search was blocked by level.

I modified my cube solver program to keep track of the number of times a search at each level failed. There are ten pieces to the puzzle, so we search at ten different levels, one level for each piece. The graph shows the number of times the search of all possible positions at that level did not find a single one that could hold the selected piece.

Levels 0 thru 4 don't even register above the X axis at this scale. Including them made the key confusing, there wasn't enough differentiation in the colors, so I didn't include them. Level 5 shows a flat line even though it has counts consistently above 10 billion (10^10). I included it just to give you an idea of the scale we are working with.

The program printed this data to stderr, which by default goes to the terminal screen. Copy and paste that into the text editor and then replace all instances of multiple spaces with a single tab. (Start with the longest sequence of spaces you can find and then work backwards.) The formatting is lost, but now you can copy and paste that into a spreadsheet and our formatting is restored.

I did some calculations in the spreadsheet to see how many comparison tests we avoided and came up with about 4.5 quadrillion, which is a very large number, but still nowhere near the value of 

12 * (3*96)^4 * (4*96)^5 = 6.8929848e+23

which is what I expected. So there is something wrong with my calculations somewhere.

P.S. Something weird happened when I pasted the text into the spreadsheet. I got a bunch of lines consisting of the single word #ERROR! I looked in my source code, but couldn't find it, and I just looked in the text file and it's not there either, so I think Google Sheets must have found something it didn't like (like a line of 300 periods) and complained. No problem, simple sort the file and all the ugly stuff you aren't interested in gets lumped together and can easily to erased.

P.P.S. One trick I use when dealing with large quantities of data is to insert a column along the left hand edge, a new column A if you will, and then number all of the lines with sequential numbers. You can easily do this by typing 1 in box A1, and then =A1+1 in box A2. Copy box A2, select all the rest of column A from A3 to the end paste. Now all the lines are numbered sequentially. However, you are not quite done. If you sort the sheet now, all the values in column A will be recomputed and your original order will be lost. So what you do is copy column A and the Paste Special -> Values Only back over it. Now you have an indelible original order. Sort however you like, but you can restore the original order by sorting on Column A.

Cube Puzzle Part 2

Recursion

I modified the program so it now finds all 335 solutions. It runs quite a bit longer now, almost 15 hours. I also uploaded a text file that illustrates all how all the transformations are done to place a piece in the cube.

The program made 41 billion comparisons, which is a bunch, but a far cry from the umpteen zillion I expected. Since the 10th root of 41 billion is only about 11, I'm thinking most searches must have reached the end of their list early on.

The program starts with the first piece placed in one of it's twelve possible positions. The first piece has only 12 possible positions as all of the other positions (276) are simply rotations of one kind or another.

We are going to test each of these against all 288 possible positions for the 2nd piece. Some of these tests will fail, indicating the pieces would collide, but most will pass. Of those that pass, we will test all 288 positions for the 3rd piece. More tests will fail at this level and fewer will pass. There will be 335 searches that will go through all of possible positions at all levels, but that only amounts to 

(12 + (3*96)*4 + (4*96)*5) = 3084

I suppose I could track how deep each search goes and perhaps a graph of the averages might give some insight, but I expect it's some kind of exponential curve. Besides, I got my solution, put the puzzle together and shipped it off to my niece. We shall see what she does with it.

Part 1 here.

Cube Puzzle

Cube Puzzle

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.

Fitting together pieces of the Cube Puzzle

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. I started working on a program to solve it earlier this week. I am not sure a brute force program can solve it in a reasonable amount of time.

Schematic representation of puzzle pieces

There are ten pieces. All pieces are one unit thick. There are five pieces with gross outer dimensions of 2 x 4 and five pieces that are 3 x 3.

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.

Cube Puzzle Solved

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.

Solution

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.

All solutions found so far here.

P.S. In the course of writing this, I realized that there may be more solutions that my program did not uncover. As soon as I found one solution, I went back to beginning and went to next mask for the first piece. Perhaps I will rectify this shortcoming. Someday. Maybe.