001 #! /usr/bin/env python
002 # -*- coding: utf-8 -*-
003 #生成华容道所有可能的终局
004 #
005 #讨论参见: http://groups.google.com/group/pongba/browse_thread/thread/a49ec9fd9541e28f
006 #---------------------------------------------------------------
007 #  Definitions
008 #    B(4): Block, 2x2
009 #    V(2): Vertical, 1x2
010 #    H(3): Horizontal, 2x1
011 #    D(1): Dot, 1x1
012 #    E(0): the empty 1x1(or space)
013 #    U(7): undefined, or (?)
014 Block,Vertical,Horizontal,Dot,Empty,Undef = 4,2,3,1,0,7
015 row, col = 5, 4
016
017 #---------------------------------------------------------------
018 #  Generates all the valid end matrix
019 #
020 C72 = ((0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6),
021        (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
022        (2, 3), (2, 4), (2, 5), (2, 6),
023        (3, 4), (3, 5), (3, 6),
024        (4, 5), (4, 6),
025        (5, 6))
026 #Possible endings(mirror ending is not included)
027 #  Ending 1: ????    Ending 2: ????
028 #            ????              ????
029 #            ????              ?EE?
030 #            EBB?              ?BB?
031 #            EBB?              ?BB?
032 endings = ([7,7,7,7,  7,7,7,7,  7,7,7,7,  0,4,4,7,  0,4,4,7],
033            [7,7,7,7,  7,7,7,7,  7,0,0,7,  7,4,4,7,  7,4,4,7])
034
035 def print_matrix(m):
036     for i in range(5):
037         for j in range(4):
038             print m[4*i + j],
039         print
040     print
041
042 def all_ending_layouts():
043     """Check all possible configurations when CaoCao is at the exit."""
044     for end in endings:
045         #14 undefined cells, red & black, select 4, 2 red & 2 black
046         slot = [i for i in range(20) if Undef == end[i]]
047         red = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2 == 0]
048         black = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2]
049         # 21 = C(7,2)
050         for c1 in C72:
051             for c2 in C72:
052                 matrix = end[:]
053                 matrix[red[c1[0]]] = Dot
054                 matrix[red[c1[1]]] = Dot
055                 matrix[black[c2[0]]] = Dot
056                 matrix[black[c2[1]]] = Dot
057                 for layout in tile(matrix):
058                     yield layout
059
060 def is_neighbor(slot, i, j):
061     xi, yi = slot[i] % col, slot[i] / col
062     xj, yj = slot[j] % col, slot[j] / col
063     if xj==xi and yj==yi+1:
064         return 2
065     if xj==xi+1 and yj==yi:
066         return 3
067     return 0
068
069 def tile(matrix):
070     """return the valid layout to tile five 1x2/2x1 in 10 slots"""
071     matrix_list = [matrix]
072     index = 0
073     while index < len(matrix_list):
074         matrix = matrix_list[index]
075         slot = [i for i in range(20) if Undef == matrix[i]]
076         n = len(slot)
077         if n == 0:
078             return matrix_list[index:]
079
080         #for each undefined block, look up its adjacent undefined block's
081         p = [[] for i in range(n)]
082         min_p, k = n, -1
083         for i in range(n):
084             for j in range(i+1, n):
085                 ret = is_neighbor(slot, i, j)
086                 if ret:
087                     p[i].append((j, ret))
088                     p[j].append((i, ret))
089             if not p[i]:
090                 k = -1
091                 break #an isolated block is detected
092             if len(p[i]) < min_p:
093                 min_p, k = len(p[i]), i
094         if k != -1:
095             #start with the position with the least adjacent undefined slots, enumerate all
096             # possible configurations after filling this position
097             for neighbor in p[k]:
098                 new_matrix = matrix[:]
099                 new_matrix[slot[k]] = neighbor[1]
100                 new_matrix[slot[neighbor[0]]] = neighbor[1]
101                 matrix_list.append(new_matrix)
102         #process next matrix
103         index += 1
104     return []
105
106 #print layouts count
107 count = 0
108 for layout in all_ending_layouts():
109     count += 1
110     print_matrix( layout )
111     #print layout
112
113 print "Total:", count