Solves a 3D wooden puzzle thing we got for christmas.

puzzle.py

# Script to solve a wooden 3D puzzle thing someone got for christmas.
# Two-colored tiles should be placed in layers so that no color appears twice 
# in each layer or in each column.
#
# Outputs:
#We have a solution!
#       Pink  ,Red    Orange,Yellow Grey  ,Green  
#Blue  ,Yellow Pink  ,Green  Grey  ,Orange 
#       Blue  ,Grey   Pink  ,Orange Green ,Red    
#Orange,Red    Yellow,Grey   Pink  ,Blue   
#       Green ,Orange Red   ,Blue   Pink  ,Yellow 
#Pink  ,Grey   Green ,Blue   Red   ,Yellow 
#       Orange,Blue   Yellow,Green  Red   ,Grey   

import sys
import itertools

RED = 1
PINK = 2
ORANGE = 3
YELLOW = 4
GREY = 5
GREEN = 6
BLUE = 7

layers = [[(PINK, RED), (ORANGE, YELLOW), (GREY, GREEN)],
          [(BLUE, YELLOW), (PINK, GREEN), (ORANGE, GREY)],
          [(RED, GREEN), (BLUE, GREY), (PINK, ORANGE)],
          [(GREY, YELLOW), (ORANGE, RED), (PINK, BLUE)],
          [(ORANGE, GREEN), (PINK, YELLOW), (BLUE, RED)],
          [(PINK, GREY), (BLUE, GREEN), (RED, YELLOW)],
          [(BLUE, ORANGE), (RED, GREY), (YELLOW, GREEN)]]

NAME = ["", "Red   ",
            "Pink  ",
            "Orange",
            "Yellow",
            "Grey  ",
            "Green ",
            "Blue  "]

def flipped(piece):
    return ((piece[1], piece[0]))
    
def combine(piece, mutations):
    return [[piece] + x for x in mutations]

def mutations_of_layer(layer):
    if len(layer) == 0:
        return [[]]
    mutations = []
    for i in range(len(layer)):
        piece = layer[i]
        other_pieces = layer[:i] + layer[i+1:]
        other_mutations = mutations_of_layer(other_pieces)
        mutations += combine(piece, other_mutations)
        mutations += combine(flipped(piece), other_mutations)
    return mutations

def flatten_layer(layer):
    return list(itertools.chain.from_iterable(layer))

def fix_stack(stack):
    def fixR(s):
        if len(s) == 0:
            return []
        flat = flatten_layer(s[0])
        flat = flat[1:] + [flat[0]]
        return [flat] + fix(s[1:])
    def fix(s):
        if len(s) == 0:
            return []
        return [flatten_layer(s[0])] + fixR(s[1:])
    return fix(stack)

def inverse_list(lst):
    return [[lst[x][y] for x in range(len(lst))] for y in range(len(lst[0]))]

def uniq(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

def is_unique(seq):
    return seq == uniq(seq)

def is_legal_stack(stack):
    fixed = fix_stack(stack)
    columns = inverse_list(fixed)
    for column in columns:
        if not is_unique(column):
            return False
    return True    

def print_stack(stack):
    fix = True
    for layer in stack:
        if fix:
            sys.stdout.write("       ")
        fix = not fix
        for piece in layer:
            sys.stdout.write(NAME[piece[0]]+","+NAME[piece[1]]+" ")
        sys.stdout.write("\n")

def find_solution(layers, stack):
    if len(layers) == 0:
        print("We have a solution!")
        print_stack(stack)
        return stack
    layer = layers[0]
    other_layers = layers[1:]
    for mut in mutations_of_layer(layer):
        if is_legal_stack(stack + [mut]):
            s = find_solution(other_layers, stack + [mut])
            if s is not None:
                return s
    return None

find_solution(layers, [])