# -*- Mode: Python -*-
#
# Sam Rushing (http://www.nightmare.com/~rushing)
#
# 3d squares puzzle.
# contruction vehicles spanning squares,
# nine of them arranged in a 3x3 grid.
#
# kinds of pieces
# red
# blue
# up/thin
# down/thick
#
# 'up' is the yellow one that scoops from above (and has a thinner tread)
# 'down' is the yellow one that scoops from below (and has a thicker tread)
#
# each of these has a 'front' and a 'back', and can be arranged in a
# 'left' or 'right' direction.  'left' means that if you put the
# vehicle together, and orient it with the wheels down, that the
# vehicle will be travelling to the left.

# edge numbers:
# +- 3 -+
# 2     0
# +  1 -+

#
# abbreviations: rfl 'red front left' rbl 'red back left'
# 

pieces = [
    'bf df rb rf',
    'rb bb uf df',
    'rb ub ub bb',
    'rf uf uf df',
    'rf df db bb',
    'bf db uf df',
    'bf rb bf uf',
    'rf bb db ub',
    'bf rb db ub',
    ]

# tuples
pieces = [x.split() for x in pieces]

# ok, now that I've encoded them all I see that they're all left-oriented.
# phew, that simplifies things.

# so the different possible pieces are just:
# rf=4 rb=5 bf=5 bb=4 uf=5 ub=4 df=5 db=4
# 20 + 16 = 36

# ok, now to solve the puzzle

# all possible rotations of a piece
def all_rots (p):
    a, b, c, d = p
    r = [p]
    for i in range (3):
        a, b, c, d = b, c, d, a
        r.append ((a,b,c,d))
    return r

def match (a, b):
    # two pieces match if they're the same vehicle, one is the front and the other is the back.
    return a[0] == b[0] and ((a[1] == 'f' and b[1] == 'b') or ((a[1] == 'b' and b[1] == 'f')))

# my original test plan went in x/y order, but I got an idea from here:
# http://www.floorsoup.com/asu-kevinburger/scholarship/scramble/
# to start with the center position and *not* rotate it, cutting out rotated solutions.

# test plan order
# 678
# 501
# 432

test_plan = [
    # 0 no tests (i.e., any piece in any orientation in position zero)
    [],
    # 1
    [(2, (0, 0))],  # at my edge 2, I need to match the piece in position zero's edge 0.
    # 2
    [(3, (1, 1))],
    # 3
    [(0, (2, 2)), (3, (0, 1))],
    # 4
    [(0, (3, 2))],
    # 5
    [(0, (0, 2)), (1, (4, 3))],
    # 6
    [(1, (5, 3))],
    # 7
    [(1, (0, 3)), (2, (6, 0))],
    # 8
    [(1, (1, 3)), (2, (7, 0))],
    ]

def test (depth, pos):
    # run the tests for this depth
    tests = test_plan[depth-1]
    for my_index, (other, other_index) in tests:
        if not match (pos[depth-1][my_index], pos[other][other_index]):
            return False
    return True
            
def solve_depth (depth, pos, pcs):
    # pos[:depth] are filled in, try new pieces at pos[depth]
    #  and recurse on any solutions.
    for i in range (len (pcs)):
        # pick out a piece
        p = pcs[i]
        # which pieces are left over?
        pcs2 = pcs[:i] + pcs[i+1:]
        # for each rotation of <p>, but no rots for zero!
        if depth == 0:
            rots = [p]
        else:
            rots = all_rots (p)
        for pr in rots:
            # compute a new position
            pos2 = pos + [pr]
            # if it passes all the tests at that depth...
            if test (depth+1, pos2):
                if depth == 8:
                    # a solution!
                    print pos2
                else:
                    # ... then recurse to the next level
                    solve_depth (depth+1, pos2, pcs2)

if __name__ == '__main__':
    solve_depth (0, [], pieces[:])