Assembling the dice

The last weekend I went with my family to visit our relatives in another area of Germany. While we were staying at my cousins house, I found these six pieces with strange edges that can be build up to a dice. I could not figure it out, so I decided to come a with a simple algorithm to solve the problem. When we came back to our home, I implemented it. It took me a little to get the interactions right but I finally did it and had an application that tells me how to put these pieces together. In this post I want to share some of the functions I coded for my approach. I do know that my solution might not be the best, fastest or shortest. Anyway!

So I took a picture of the pieces to build an assembler. I took it with my cell so the quality is not the best.

02082009053

Now about the code. I wanted to place the snippets here and have them formatted automatically C# style but I could not find a working solution that did not take me too long to setup, figure out how it is working or why it is not working at all! So I ended up using screenshots.

image

What is on the picture above is the Main method of my console application. I initialize a dice object by linking its six sides together so that I can easily get references to all surrounding sides of every side by an edge classifier enumeration. This object works like a stub and accepts one of the six pieces to be applied to each side. Once the dice is in memory, I create a DiceMagician (I thought the name is fun) and hand him over all the pieces to build the dice. I give him an action object as well, so he can notify me on every solution he finds.

The solution finding implements a simple recursive back tracking approach. I iterate over all empty sides of the dice and for each side over all unused pieces. Each piece is going to be tried to put it on the current side in one of its mutation. As a mutation the pieces turn and flip so that they are tried eight times each to put it on. If it can be put on, the recursion starts over with all the left sides and pieces. If it can not be put, the recursion ends and tries the next mutation, piece or side.

image

When all the pieces could be placed on a side of the dice, a solution has been found. Then the caller is notified about it by executing the foundAction function. The interesting part here is where the decision is made whether a piece can be applied. The corresponding side needs to check if the neighbor sides pieces do allow it. Therefore it invokes the IsFree method on all these surrounding sides.

image

So the sides receive the invocation and check if the edge (form where the request is coming) of the applied piece has an edge that dove-tails with the corresponding edge of the piece that is tried to put on. I am checking on each position of that edge. It can happen that the x or y coordinates of the two pieces are aligned counterclockwise. To deal with this, I let an iteration mapping per edge decide how the coordinates flow.

image

When the dice is assembled and the sides are linked together, I need to declare which edges are going to face a reversed alignment of coordinates when checking of availability. So the sides that are registered by one another can be linked by normal or reversed edge. Depending on that, there are different iteration actions used. While a normal edge iterates on both connected sides in the same direction, a reversed edge iterates in different directions. This is why my iteration loop has two arguments, i and j. The first is counting down, the second up. When the side is checking with the other side, they can do that by using i and j without the need to know what values they are going to be. The values are determined by the kind of edge that is in between the two sides.

image

So this is it. When I run the application I get the solutions of how to assemble the dice directly written onto the console. Unfortunately I do not have the pieces so I can not actually build the dice. I also have no idea how many solutions the program will find but there must be a lot of solutions that are ultimately the same and just describe the dice from different perspectives. Feel free to download the application.

image 

http://cid-e6c5570276bdbe2b.skydrive.live.com/embedrowdetail.aspx/%c3%96ffentlich/Assemble6PiecesDice.exe

 

Ok, this was a different blog post and I do not believe anybody actually read it all. Anyway, follow me on Twitter: @halllo and check out my website: www.neokc.de!

Manuel Naujoks

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s