gen_tiling.py

import sys
import copy

def gen_emp_tree(num):
    l = []
    for i in range(4):
        l.append(['']*num)
    return l


def is_not_good(l):
    n = len(l[0])

    for i in range(4):
        for j in range(n):
            if j < n-1 and l[i][j] == '' and l[i][j+1] == '':
                return False

            if i < 3 and l[i][j] == '' and l[i+1][j] == '':
                return False

    return True


def add_horz_2(l):
    n = len(l[0])

    for i in range(4):
        for j in range(n-1):
            if l[i][j] == '' and l[i][j+1] == '':
                l[i][j] = l[i][j+1] = 'h'
                return l

    return None

def add_vert_2(l):
    n = len(l[0])

    for i in range(3):
        for j in range(n):
            if l[i][j] == '' and l[i+1][j] == '':
                l[i][j] = l[i+1][j] = 'v'
                return l

    return None


def add_2by2(l):
    n = len(l[0])

    for i in range(3):
        for j in range(n-1):
            if l[i][j] == '' and l[i][j+1] == '' and l[i+1][j] == '' and l[i+1][j+1] == '':
                l[i][j] = l[i][j+1] = l[i+1][j] = l[i+1][j+1] = 'H'
                return l

    return None


def gen_trees(l):
    if is_not_good(l):
        return l

    n = []

    horz2 = add_horz_2(copy.deepcopy(l))
    if horz2:
        n += gen_trees(horz2)

    vert2 = add_vert_2(copy.deepcopy(l))
    if vert2:
        n += gen_trees(vert2)

    horz2by2 = add_2by2(copy.deepcopy(l))
    if horz2by2:
        n += gen_trees(horz2by2)

    return n

def main():
    if len(sys.argv) != 2:
        print 'give me one num'
        sys.exit(1)
    else:
        num = int(sys.argv[1])

    l = gen_emp_tree(num)
    l = gen_trees(l)

    lst = []
    for i in range(len(l)):
      if not i % 4:
            check = True
            tmp = l[i] + l[i+1] + l[i+2] + l[i+3]
            try:
                tmp.index('')
                check = False
            except:
                pass

            if check:
                tmp = [l[i], l[i+1], l[i+2], l[i+3]]
                try:
                    lst.index(tmp)
                except:
                    lst.append(tmp)

    # Print all possible combinations
    for i in lst:
        for j in i:
            print j
        print ''

    print len(lst)

if __name__ == '__main__':
    main()