#! /usr/bin/env python
# -*- coding: utf-8 -*-
#生成华容道所有可能的终局
#
#讨论参见: http://groups.google.com/group/pongba/browse_thread/thread/a49ec9fd9541e28f
#---------------------------------------------------------------
#  Definitions
#    B(4): Block, 2x2
#    V(2): Vertical, 1x2
#    H(3): Horizontal, 2x1
#    D(1): Dot, 1x1
#    E(0): the empty 1x1(or space)
#    U(7): undefined, or (?)
Block,Vertical,Horizontal,Dot,Empty,Undef = 4,2,3,1,0,7
row, col = 5, 4

#---------------------------------------------------------------
#  Generates all the valid end matrix
#
C72 = ((0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6),
       (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
       (2, 3), (2, 4), (2, 5), (2, 6),
       (3, 4), (3, 5), (3, 6),
       (4, 5), (4, 6),
       (5, 6))
#Possible endings(mirror ending is not included)
#  Ending 1: ????    Ending 2: ????
#            ????              ????
#            ????              ?EE?
#            EBB?              ?BB?
#            EBB?              ?BB?
endings = ([7,7,7,7,  7,7,7,7,  7,7,7,7,  0,4,4,7,  0,4,4,7],
           [7,7,7,7,  7,7,7,7,  7,0,0,7,  7,4,4,7,  7,4,4,7])

def print_matrix(m):
    for i in range(5):
        for j in range(4):
            print m[4*i + j],
        print
    print

def all_ending_layouts():
    """Check all possible configurations when CaoCao is at the exit."""
    for end in endings:
        #14 undefined cells, red & black, select 4, 2 red & 2 black
        slot = [i for i in range(20) if Undef == end[i]]
        red = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2 == 0]
        black = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2]
        # 21 = C(7,2)
        for c1 in C72: 
            for c2 in C72:
                matrix = end[:]
                matrix[red[c1[0]]] = Dot
                matrix[red[c1[1]]] = Dot
                matrix[black[c2[0]]] = Dot
                matrix[black[c2[1]]] = Dot
                for layout in tile(matrix):
                    yield layout

def is_neighbor(slot, i, j):
    xi, yi = slot[i] % col, slot[i] / col
    xj, yj = slot[j] % col, slot[j] / col
    if xj==xi and yj==yi+1:
        return 2
    if xj==xi+1 and yj==yi:
        return 3
    return 0

def tile(matrix):
    """return the valid layout to tile five 1x2/2x1 in 10 slots"""
    matrix_list = [matrix]
    index = 0
    while index < len(matrix_list):
        matrix = matrix_list[index]
        slot = [i for i in range(20) if Undef == matrix[i]]
        n = len(slot)
        if n == 0:
            return matrix_list[index:]

        #for each undefined block, look up its adjacent undefined block's
        p = [[] for i in range(n)]
        min_p, k = n, -1
        for i in range(n):
            for j in range(i+1, n):
                ret = is_neighbor(slot, i, j)
                if ret:
                    p[i].append((j, ret))
                    p[j].append((i, ret))
            if not p[i]:
                k = -1
                break #an isolated block is detected
            if len(p[i]) < min_p:
                min_p, k = len(p[i]), i
        if k != -1:
            #start with the position with the least adjacent undefined slots, enumerate all
            # possible configurations after filling this position
            for neighbor in p[k]:
                new_matrix = matrix[:]
                new_matrix[slot[k]] = neighbor[1]
                new_matrix[slot[neighbor[0]]] = neighbor[1]
                matrix_list.append(new_matrix)
        #process next matrix
        index += 1
    return []

#print layouts count
count = 0
for layout in all_ending_layouts():
    count += 1
    print_matrix( layout )
    #print layout

print "Total:", count