Posted by: Josh | September 29, 2008

Project Complete: Tetris Cube Solver Cloud

aka TetrisCubing@Home

Update:

If you’re looking a step-by-step solution, you can find it now here.

The Objective

The TetrisCubing@Home project was founded in an effort to solve the “deceptively simple” Tetris Cube block puzzle. This puzzle consists of a 4x4x4 box with 12 uniquely shaped pieces that range from a volume of 4 to 6 1x1x1 cubes (hereon defined as “cubits”).

According to the puzzle’s packaging, there are almost 10,000 possible solutions, of which Lee, Esther, Ian, Vince  and I had found 0 by hand. It’s true – this puzzle was deceptively simple – how hard could it be to put 12 pieces back into a formation if there were so many solutions?

As a good computer scientist, I took it into my hands to put the pieces back in their rightful place. Searching for a solution on Google would clearly be cheating – where’s the fun in that?

Inspired by such projects as Folding@Home I began to search for a solution…

The Idea

Each piece can be rotated in 24 unique ways (not 6; orientation matters), and if you visualize it as a 1x1x1 cube, can be placed potentially in 64 positionsin the cube (4x4x4).

Since there are 12 pieces, our potential worst case scenario could see a total of approximately (24*64)^12 = 1.7 x 10^38 combinations! However, if we take into account piece collisions, this number should be a lot smaller.

Even though finding the solution will occur most likely before all the scenarios are tested, this would still be a daunting task for a single computer to handle. Speeding up this process is accomplished through teamwork. It works much like the Folding@Home protein computation project: the task is broken down into several sub-tasks which are much more manageable.

The Implementation

How does this work? The TetrisCubing@Home server has a database containing a index of all the possible combinations that a certain 4 pre-defined blocks can be placed in the 4x4x4 cube. Each combination of the four blocks represents a “work piece”.

When a client contacts a server and requests for work, it is assigned a work piece. Using that work piece’s data, the client will position the four blocks according to the work piece specifications. It will then proceed to insert the other eight work pieces in all possible configurations around those blocks. If it succeeds, it will inform both the server and the user of the accomplishment. Otherwise, it will contact the server informing of the failure, and the server will keep a log of this progress and assign the client another work piece.

Essentially, multiple instances of my brute-force approach application can systematically go through all possible cube formations together, tracked by one central server (in fact, I originally had this as a standalone application, but after running it for one whole week on my Thinkpad T61 with no end in sight, I aborted that plan).

So I had a bunch of good friends (with several cycles to spare!) run several instances of my client. Works great with multi-core processors!

In addition to their current workload status, they could also check in real-time how they were doing compared to everyone else. Here’s the original statistics page:

———————————————————-

TetrisCubing@Home Server Statistics

You must be running client v0.71 to join the Collective.

1,475/7,394,542 work pieces completed (0.01995%).
Computations so far: 1,674,572,240
Estimated computation time remaining: ~25670 workdays @ 5min/work piece for one cpu (~2 GHz).

Scoreboard: Top 10 Participants

Rank Peer Iteration Total Contribution Completed
1. joshjcarrier 673,058,151 41.08 % 606

2. bchang 316,696,370 17.08 % 252

3. sabanski_n 238,641,106 13.83 % 204

4. xuemin 166,739,829 9.9 % 146

5. timetablebuilder 115,063,400 8.81 % 130

6. mBerg 132,767,963 7.46 % 110

7. lbeckman 31,605,421 1.83 % 27

———————————————————-

Well, it wasn’t long before…

———————————————————-

MATCH FOUND!

No further client requests will be accepted until further notice.

Congratulations to sabanski_n (Nathaniel Sabanski) who found the solution in work piece #1478 in 6500543 iterations on March 6th, 2008 – 2 days after the Collective went live!

Work piece #1478 Sequence: 1:0:0:0#1:0:0:2#1:1:0:2#10:1:0:-1
Cube virtualization:

6 1 1 1     3 3  1  7      3 2 2  2     11 11 4 2
6 1 5 7     6 3  3  7     11 2 4  8     11 4 4 4
6 1 5 7     9 3 10 10     11 2 4  8     12 12 8 8
6 9 5 7     9 9  5 10     12 9 5 10     12 12 8 10

Each group of number corresponds to a different block, and each grid represents one 4×4 layer.

———————————————————-
There was actually a bug in the “match found” window that reports the wrong winning sequence, so I had to pull this data from the database. In doing so, I belive I found another winning combination by mBerg in work piece #1465, he just didn’t notify me before Nat did😛.

Estimates of a single-threaded standalone program would attempt to solve work piece #1478’s winning iteration after three weeks of constantly running! There had been a total of 14 clients working on assembling the cube.

I also found this neat blurb about winning a free iPhone if you could solve it on the spot over at CNet.

And so that’s how I finished a deceptively simple puzzle. Thanks everyone who particpated for donating their spare cycles!

Update:

If you’re looking a step-by-step solution, you can find it now here.


Responses

  1. I honestly did not imagine this happening when I bought you this. I figured we’d find a solution every few minutes or so by just messing with it. Also, have you taken it apart again since solving it?

  2. […] (what can I say, Java is awesome). Josh uses Java for many of his projects, one of which included solving a complex tetris cube using the awesome power of distributed […]

  3. […] birthday! Nat has been my long-time tech collaborator and beta tester; he helped me to solve the Tetris Cube puzzle earlier this year and run several compatibility tests without any hesitation over the years and for […]

  4. Hey guys, nice try! Please take a look into this webpage to see all of the 9,839 solutions for the cube… Looks like a simple C code works much better. Bye.
    http://scottkurowski.com/tetriscube/

  5. i hate this thing

  6. i hate this thing so much i just want to smash it up

  7. […] Carrier, Tetris Cube Solver Cloud. [Josh also setup a distributed processing environment and enslaved some of his friend's computers […]

  8. I like the fact that you say searching for a soloution to this on google is cheating. Although you put all the information into your computer and let that do all the work. In my opinion that is clearly cheating too! The only way to not cheat would be to do it the old fashioned way and use your hands!!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Categories

%d bloggers like this: