Intel's Ronler Acres Plant

Silicon Forest
If the type is too small, Ctrl+ is your friend

Sunday, October 18, 2020

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.

No comments: