The CubeQuest – BruteForcing to a solution

This one came as a birthday present. Immediatly after unwrapping the present, the instructions to put all parts together were taken away as I was certain I could do it in a reasonably time. But as almost always, pride will have a fall. After 1 hour I thought:

Wouldn’t it be easier to calculate the solution?

This timber puzzle game is made of 25 parts. Each the same shape: a four unit long stick with a “nose” of 1 unit at the second unit. These parts are sometimes called Y-parts. All parts must be put together to a cube of 5x5x5 units – tighly packed so to say. A bit like Tetris but with only one shape and in 3D. From that moment on I stopped trying to solve the puzzle myself and instead thought about ways to code a solver that could do all the work.

Imagine all 25 parts in a combination as a path from a tree trunk over branches and more branches to every tiny leaf, and every combination is a different path to another leaf and then try to guess how many leaves this tree must have! And only 1 or a few out of all leaves are the special golden ones you want to find.

As I progressed towards the first real code it became very intimidating. The CIMG4787number of possible combinations seemed so huge and after some deep thought into that almost impossible to calculate as well. So I wanted a program that tries every possible combination of 25 timber parts in 3D with nearly endless iterations? Wouldn’t that take at least “very” long? I was very unsure about persuing my goal any further but kept on going.

After some time the first prototype of my program started to work for me. The strategy was very easy at first:

  1. Take a part, put it in the playing field
  2. Don’t overlap with any existing parts
  3. Repeat steps 1+2 until the solution or the more probable dead end
  4. Take away the last part and try another orientation of that part
  5. Repeat steps 1-4 until at least 1 solution is found

I soon realiezed that this strategy was good, but very slow. The number of iterations per seconds was around 1000. Only sounds good at first. The problem is that all these iterations where distinct leaves. No way 1000 i/s could beat all the combinations in a matter of even years. So I needed better ways to sort out whole branches, meaning to see earlier on a path if it was a dead end.

There are some cases in which a human would see those dead ends miles ahead because it is plain simple. Like when there is a hole between the parts that no next part can ever fill, then it’s pointless to go on. The part creating that hole must be placed wrong.
Or when the space between the parts that have already been placed and the boundaries of the playing ground make a hole that no next part can fill its pointless to go on again.

1st visualizationIn addition to the above 2 thoughts I wanted to let a minimum of double checks of the same 3D-representions of 25 placed parts. You can think of it as a different path to the same leaf of the tree. Either way if the leaf isn’t special you can ignore all paths to it. So how to ignore double paths? I did not know exactly but I made some improvements that were supposed to help with that. For example, there must be only 1 conjoined space with all free spaces of the playing field. If a placed part splits the remaining space into 2 seperate areas then ignore this whole branche because the space can be filled another way. Meaning: There must be a different path to the same leaf that doesn’t split the remaining space. And for that let’s only continue adding parts near existing parts.

So the computer tried more and more combinations. When the program ran it took all the cpu power it could get, making it impossible to work or play on the computer any more. So I thought of a way to pause and resume the calculation: Instead of saving the paths the program checked the (incomplete) paths of promising combinations were saved in a file. It looked something like this:

0,0,0|3,0,0|2,1,0#4,0,0|0,0,3|0,1,1
0,0,0|3,0,0|2,1,0#4,0,0|0,0,3|0,1,2#1,2,2|3,0,0|1,1,0
0,0,0|3,0,0|2,1,0#4,0,0|0,0,3|0,1,2#4,2,1|0,0,3|0,1,2
0,0,0|3,0,0|2,1,0#4,0,0|0,0,3|0,1,2#4,2,1|0,0,3|0,-1,2#1,3,4|3,0,0|1,1,0

Each line means a promising part of a path. Each # seperates a part from the other, the | seperates the origin vector, the “long vector” and the “nose vector” so each part is positioned in a well-defined way. When a line ends it means that all paths from that point on must be examinated. So when there is a longer line it simply means the path is more “described” and there are fewer combinations to be tested upon this path of parts.

In the end, after hours of computing time bruteforcing through all the combinations the computer gave me this line:

0,0,0|3,0,0|2,1,0#0,1,0|0,0,3|0,-1,1#0,0,2|3,0,0|2,0,-1#0,0,3|3,0,0|2,0,1#0,0,4|0,3,0|0,2,-1#0,2,0|3,0,0|2,1,0#0,2,1|3,0,0|2,-1,0#0,2,2|3,0,0|2,-1,0#0,3,0|0,0,3|1,0,2#0,4,0|3,0,0|1,-1,0#0,4,1|0,0,3|1,0,1#1,1,0|0,0,3|0,-1,1#1,0,4|0,3,0|1,2,0#1,2,3|3,0,0|1,-1,0#1,3,1|3,0,0|2,0,1#1,3,3|3,0,0|1,0,-1#1,4,1|3,0,0|2,0,1#1,4,3|3,0,0|1,0,-1#1,4,4|3,0,0|1,-1,0#3,0,4|0,3,0|-1,1,0#3,1,0|0,0,3|0,-1,1#4,1,0|0,3,0|-1,2,0#4,0,0|0,0,3|0,1,1#4,0,4|0,3,0|0,1,-1#4,1,2|0,3,0|0,1,-1

Could that be the solution?

In fact it was, as I found out when I couriously took the wooden parts and carefully put them together while reading my newly created instructions! After that I let the program ran a while longer and it found more solutions.

After this problem was solved to my satisfaction I allowed myself to search the web for the solutions and found out there are 1264 solutions. Well out of millions and billions of combinations at least.

Leave a Reply

Your email address will not be published. Required fields are marked *