Puzzle Solving

This is the story of a friendly competition I engaged in with Haitao, one of my coworkers. We raced to find the solution to a plastic puzzle called the Tetris Cube that the office obtained somehow. He solved it by hand. I wrote a Python script. I didn't tell Haitao that it was a race, and it's unclear who won.

Tetris Cube consists of twelve colored, plastic, tetris-like pieces which go together to make a cube.

Here is a picture of the pieces:

This is the program I wrote:

import numpy as np

orientations = map(np.matrix, [
    [[1, 0, 0], [0, 1, 0], [0, 0, 1]],
    [[1, 0, 0], [0, 0, -1], [0, 1, 0]],
    [[1, 0, 0], [0, -1, 0], [0, 0, -1]],
    [[1, 0, 0], [0, 0, 1], [0, -1, 0]],
    [[1, 0, 0], [0, 1, 0], [0, 0, 1]],
    [[0, 0, -1], [0, 1, 0], [1, 0, 0]],
    [[-1, 0, 0], [0, 1, 0], [0, 0, -1]],
    [[0, 0, 1], [0, 1, 0], [-1, 0, 0]],
    [[1, 0, 0], [0, 1, 0], [0, 0, 1]],
    [[0, -1, 0], [1, 0, 0], [0, 0, 1]],
    [[-1, 0, 0], [0, -1, 0], [0, 0, 1]],
    [[0, 1, 0], [-1, 0, 0], [0, 0, 1]]])

piece_templates = {
    "red t/" : [(0,0,0), (1,0,0), (2,0,0), (3,0,0), (2,1,0)],
    "yellow tx" : [(1,0,0), (0,1,0), (1,1,0), (2,1,0), (1,0,1)],
    "yellow zz" : [(1,0,0), (0,1,0), (1,1,0), (1,0,1), (2,0,1)],
    "yellow t+" : [(1,0,0), (0,1,0), (1,1,0), (2,1,0), (1,1,1), (1,2,1)],
    "yellow Ll" : [(0,0,0), (1,0,0), (2,0,0), (0,0,1), (0,1,1)],
    "red T," : [(2,0,0), (0,1,0), (1,1,0), (2,1,0), (1,2,0), (2,0,1)],
    "red O'" : [(0,0,0), (1,0,0), (1,1,0), (0,1,0), (0,0,1)],
    "red L" : [(0,0,0), (1,0,0), (2,0,0), (0,1,0), (0,2,0)],
    "blue L'" : [(0,0,0), (1,0,0), (2,0,0), (0,1,0), (0,2,0), (1,0,1)],
    "blue z" : [(0,0,0), (1,0,0), (2,0,0), (2,1,0), (3,1,0)],
    "blue zl" : [(1,0,0), (2,0,0), (0,1,0), (1,1,0), (2,0,1)],
    "blue rl" : [(0,0,0), (1,0,0), (2,0,0), (0,1,0), (2,0,1), (2,0,2)]}


def transform(m, piece):
    def t(p):
        y = p*m
        return (y.item(0), y.item(1), y.item(2))
    return set(map(t, piece))

def translate(v, piece):
    def t(p):
        return (v[0]+p[0], v[1]+p[1], v[2]+p[2])
    return set(map(t, piece))

def extreme(foo, index, piece):
    def t(p):
        return p[index]
    return reduce(foo, map(t, piece))

def all_fits(pt):
    result = []
    for m in orientations:
        piece = transform(m, pt)
        for i in range(-extreme(min, 0, piece), 4-extreme(max, 0, piece)):
            for j in range(-extreme(min, 1, piece), 4-extreme(max, 1, piece)):
                for k in range(-extreme(min, 2, piece), 4-extreme(max, 2, piece)):
                     result.append(translate((i,j,k), piece))
    return result


initial_fitmap = {}
for name in piece_templates:
    initial_fitmap[name] = all_fits(piece_templates[name])


def solve(piecesplaced, fitmap):
    if len(fitmap)==0:
        i = 0
        print '\n'
        for name in initial_fitmap:
            print name, piecesplaced[i]
            i+=1
        print '\n'
        return

    newfitmap = {}

    dirt = set().union(*piecesplaced)
    def cull(s):
        return dirt.isdisjoint(s)

    firstname = fitmap.keys()[0]

    firstfit = filter(cull, fitmap[firstname])
    if len(firstfit) == 0:
        return

    for name in fitmap.keys()[1:]:
        newfit = filter(cull, fitmap[name])
        if len(newfit) == 0:
            return
        newfitmap[name] = newfit

    for piece in firstfit:
        solve(piecesplaced + [piece], newfitmap)


print "solving..."
solve([], initial_fitmap)
print "... done solving"

Haitao started solving the puzzle by hand using wits and elbow-grease. I secretly wrote the program and left it running over night. The next day, I saw a printed solution on my screen. Haitao still had the pieces at his desk. He finished the puzzle that morning. Then later I verified that the program's solution was correct, by assembling by hand according to the program's output.

So, who was the winner? Hard to call.