代码
比这篇新的文章:
test
比这篇旧的文章: 密码转换
作者: 半瓶墨水, 点击1557次, 评论(1), 收藏者(0), , 打分:
所有评论，共1条：( 我也来说两句)
比这篇旧的文章: 密码转换
华容道结局的所有组合
语言: Python, 标签: 华容道 终局 2008/10/26发布 1年前更新 更新记录作者: 半瓶墨水, 点击1557次, 评论(1), 收藏者(0), , 打分:
Python语言: 华容道结局的所有组合
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
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
所有评论，共1条：( 我也来说两句)
| 1 |
lxl
1年前
回复
代码不错，最近开始重新学C，得好好研究研究
|