001 #! /usr/bin/env python
002 # -*- coding: utf-8 -*-
003 #华容道所有开局求解:
004 # 1. 生成所有终局
005 # 2. 广度优先推出所有开局，形成一个树
006 # 3. 树中所有的节点都是开局，可以根据Level进行排序
007 #
008 #讨论参见: http:#groups.google.com/group/pongba/browse_thread/thread/a49ec9fd9541e28f
009 #---------------------------------------------------------------
010 #  Definitions
011 #    B(4): Box, 2x2
012 #    V(2): Vertical Bar, 1x2
013 #    H(3): Horizontal Bar, 2x1
014 #    D(1): Dot, 1x1
015 #    E(0): the empty 1x1(or space)
016 #    U(7): undefined, or (?)
017 Empty,Dot,Vbar,Hbar,Box,Undef = 0,1,2,3,4,7
018 row, col = 5, 4
019
020 #---------------------------------------------------------------
021 #  Generates all the valid end matrix
022 #
023 C72 = ((0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6),
024        (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
025        (2, 3), (2, 4), (2, 5), (2, 6),
026        (3, 4), (3, 5), (3, 6),
027        (4, 5), (4, 6),
028        (5, 6))
029 #Possible endings(mirror ending is not included)
030 #  Ending 1: ????    Ending 2: ????
031 #            ????              ????
032 #            ????              ?EE?
033 #            EBB?              ?BB?
034 #            EBB?              ?BB?
035 endings = ([7,7,7,7,  7,7,7,7,  7,7,7,7,  0,4,4,7,  0,4,4,7],
036            [7,7,7,7,  7,7,7,7,  7,0,0,7,  7,4,4,7,  7,4,4,7])
037
038 def print_matrix(m):
039     for i in range(5):
040         for j in range(4):
041             print m[4*i + j],
042         print
043     print
044
045 def all_ending_layouts():
046     """Check all possible configurations when CaoCao is at the exit."""
047     values = {}
048     for end in endings:
049         #14 undefined cells, red & black, select 4, 2 red & 2 black
050         slot = [i for i in range(20) if Undef == end[i]]
051         red = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2 == 0]
052         black = [slot[i] for i in range(14) if (slot[i] % col + slot[i] / col) % 2]
053         # 21 = C(7,2)
054         for c1 in C72:
055             for c2 in C72:
056                 matrix = end[:]
057                 matrix[red[c1[0]]] = Dot
058                 matrix[red[c1[1]]] = Dot
059                 matrix[black[c2[0]]] = Dot
060                 matrix[black[c2[1]]] = Dot
061                 for layout in tile(matrix):
062                     value = 0L
063                     for t in layout:
064                         value = value << 3 | t
065                     if not values.has_key(value):
066                         rvalue = 0L
067                         for i in range(5):
068                             for j in range(4):
069                                 rvalue = rvalue << 3 | layout[i*4 + 4-j-1]
070                         values[value] = True
071                         values[rvalue] = True
072                         yield layout
073
074 def is_neighbor(slot, i, j):
075     xi, yi = slot[i] % col, slot[i] / col
076     xj, yj = slot[j] % col, slot[j] / col
077     if xj==xi and yj==yi+1:
078         return 2
079     if xj==xi+1 and yj==yi:
080         return 3
081     return 0
082
083 def tile(matrix):
084     """return the valid layout to tile five 1x2/2x1 in 10 slots"""
085     matrix_list = [matrix]
086     index = 0
087     while index < len(matrix_list):
088         matrix = matrix_list[index]
089         slot = [i for i in range(20) if Undef == matrix[i]]
090         n = len(slot)
091         if n == 0:
092             return matrix_list[index:]
093
094         #for each undefined block, look up its adjacent undefined block's
095         p = [[] for i in range(n)]
096         min_p, k = n, -1
097         for i in range(n):
098             for j in range(i+1, n):
099                 ret = is_neighbor(slot, i, j)
100                 if ret:
101                     p[i].append((j, ret))
102                     p[j].append((i, ret))
103             if not p[i]:
104                 k = -1
105                 break #an isolated block is detected
106             if len(p[i]) < min_p:
107                 min_p, k = len(p[i]), i
108         if k != -1:
109             #start with the position with the least adjacent undefined slots, enumerate all
110             # possible configurations after filling this position
111             for neighbor in p[k]:
112                 new_matrix = matrix[:]
113                 new_matrix[slot[k]] = neighbor[1]
114                 new_matrix[slot[neighbor[0]]] = neighbor[1]
115                 matrix_list.append(new_matrix)
116         #process next matrix
117         index += 1
118     return []
119
120 #---------------------------------------------------------------
121 # spawn all the layouts to be solved
122
123 #convert 4*5 DHVB into block layouts(totally 10 blocks)
124 def convert(matrix):
125     b = [0, 0, 0, 0]
126     c,d = 0,0
127     result = []
128     for i in range(20):
129         x = i % 4
130         y = i / 4
131         n = matrix[i]
132         if n == Dot:
133             result += [1, x, y]
134         elif n == Vbar:
135             if y == 0 or b[x] == 0:
136                 b[x] = 2
137                 result += [2, x, y]
138             else:
139                 b[x] = 0
140         elif n == Hbar:
141             if c == 0:
142                 result += [3, x, y]
143                 c = 3
144             else:
145                 c = 0
146         elif n == Box:
147             if d % 4 == 0:
148                 result += [4, x, y]
149                 d = 1
150             else:
151                 d += 1
152     return result
153
154 from copy import deepcopy
155
156 class Board:
157     def __init__(self, layout):
158         #the moved index to generate this board
159         self.moved = -1
160         #init the matrix and items
161         self.items = [()] * 10 #BIT:type:3,x:2,y:3), x,y is zero-based
162         self.empty = [(0,0), (0,0)] #2 empty slot's position in matrix, (col, row)
163
164         #-1 mean's boundary
165         f = -1
166         #[1+5+1][1+4+1] of byte, each byte is the (index+1) in items
167         #  the extra 1s is for the boundary
168         self.matrix = [ [f, f, f, f, f, f],
169                         [f, 0, 0, 0, 0, f],
170                         [f, 0, 0, 0, 0, f],
171                         [f, 0, 0, 0, 0, f],
172                         [f, 0, 0, 0, 0, f],
173                         [f, 0, 0, 0, 0, f],
174                         [f, f, f, f, f, f] ]
175
176         #calculate the items into cell-matrix
177         type, x, y = 0, 0, 0
178         for i in range(10):
179             type = layout[i*3]
180             x = layout[i*3+1]
181             y = layout[i*3+2]
182             self.items[i] = (type, x, y)
183             self.matrix[y+1][x+1] = i+1
184             if type == Vbar:
185                 self.matrix[y+2][x+1] = i+1
186             elif type == Hbar:
187                 self.matrix[y+1][x+2] = i+1
188             elif type == Box:
189                 self.matrix[y+1][x+2] = i+1
190                 self.matrix[y+2][x+1] = i+1
191                 self.matrix[y+2][x+2] = i+1
192         #find out the empty blocks
193         count = 0
194         for i in range(7):
195             for j in range(6):
196                 if not self.matrix[i][j]:
197                     self.empty[count] = (j, i)
198                     if not count: count += 1
199                     else: return
200
201     def getValue(self):
202         val, bt = 0L, 0
203         for i in range(1, 6):
204             for k in range(1, 5):
205                 index = self.matrix[i][k] - 1
206                 if index < 0: bt = 0
207                 else: bt = self.items[index][0]
208                 val = val << 3 | bt
209         return val
210
211     def getRValue(self):
212         val, bt = 0L, 0
213         for i in range(1, 6):
214             for k in range(4, 0, -1):
215                 index = self.matrix[i][k] - 1
216                 if index < 0: bt = 0
217                 else: bt = self.items[index][0]
218                 val = val << 3 | bt
219         return val
220
221     #spawn new Board by moving the cells around empty cells
222     #  changes global variable: g_values
223     def spawn(self):
224         global g_values
225         new_boards = []
226         #collect the cells around empty cells
227         around = [0] * 8
228         #DO NOT change the order of ulrd, it's been depended
229         #       ulrd: Up/Left/Right/Down
230         ulrd = ((0,-1), (-1,0), (1,0), (0,1))
231         for e in self.empty: #two empty blocks, always 2
232             x, y = e
233             for k in range(4):
234                 dir = ulrd[k]
235                 nx = x + dir[0]
236                 ny = y + dir[1]
237                 index = self.matrix[ny][nx] - 1
238                 if index >= 0:
239                     newb = deepcopy(self)
240                     newb.moved = index
241                     if newb.tryAndMove(index, -dir[0], -dir[1]):
242                         value = newb.getValue()
243                         if not g_values.has_key(value):
244                             if len(g_values) % 1000 == 0:
245                                 print len(g_values)
246                             rvalue = newb.getRValue()
247                             g_values[value] = rvalue
248                             g_values[rvalue] = value
249                             new_boards.append(newb)
250         return new_boards
251
252     def tryAndMove(self, index, dx, dy):
253         item = self.items[index]
254         type, x, y = item
255         ret = False
256         #ci is short for cell index
257         ci1 = ci2 = ci3 = ci4 = 0
258         if type == Dot:
259             ci1 = self.matrix[y+dy+1][x+dx+1]
260             ret = not ci1 or ci1 == index+1
261             if ret:
262                 self.matrix[y+1][x+1] = 0
263                 self.matrix[y+dy+1][x+dx+1] = index + 1
264                 self.items[index] = (type, x+dx, y+dy)
265                 self.setEmpty(x+1, y+1)
266
267         elif type == Vbar:
268                 ci1 = self.matrix[y+dy+1][x+dx+1]
269                 ci2 = self.matrix[y+dy+2][x+dx+1]
270                 ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1)
271                 if ret:
272                     self.matrix[y+1][x+1] = 0
273                     self.matrix[y+2][x+1] = 0
274                     self.matrix[y+dy+1][x+dx+1] = index + 1
275                     self.matrix[y+dy+2][x+dx+1] = index + 1
276                     self.items[index] = (type, x+dx, y+dy)
277                     if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)
278                     if self.matrix[y+2][x+1] == 0: self.setEmpty(x+1, y+2)
279
280         elif type == Hbar:
281                 ci1 = self.matrix[y+dy+1][x+dx+1]
282                 ci2 = self.matrix[y+dy+1][x+dx+2]
283                 ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1)
284                 if ret:
285                     self.matrix[y+1][x+1] = 0
286                     self.matrix[y+1][x+2] = 0
287                     self.matrix[y+dy+1][x+dx+1] = index + 1
288                     self.matrix[y+dy+1][x+dx+2] = index + 1
289                     self.items[index] = (type, x+dx, y+dy)
290                     if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)
291                     if self.matrix[y+1][x+2] == 0: self.setEmpty(x+2, y+1)
292
293         elif type == Box:
294                 ci1 = self.matrix[y+dy+1][x+dx+1]
295                 ci2 = self.matrix[y+dy+1][x+dx+2]
296                 ci3 = self.matrix[y+dy+2][x+dx+1]
297                 ci4 = self.matrix[y+dy+2][x+dx+2]
298                 ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1) and \
299                       (not ci3 or ci3==index+1) and (not ci4 or ci4==index+1)
300                 if ret:
301                     self.matrix[y+1][x+1] = 0
302                     self.matrix[y+1][x+2] = 0
303                     self.matrix[y+2][x+1] = 0
304                     self.matrix[y+2][x+2] = 0
305                     self.matrix[y+dy+1][x+dx+1] = index+1
306                     self.matrix[y+dy+1][x+dx+2] = index+1
307                     self.matrix[y+dy+2][x+dx+1] = index+1
308                     self.matrix[y+dy+2][x+dx+2] = index+1
309                     self.items[index] = (type, x+dx, y+dy)
310                     if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)
311                     if self.matrix[y+1][x+2] == 0: self.setEmpty(x+2, y+1)
312                     if self.matrix[y+2][x+1] == 0: self.setEmpty(x+1, y+2)
313                     if self.matrix[y+2][x+2] == 0: self.setEmpty(x+2, y+2)
314         return ret
315
316     def setEmpty(self, ex, ey):
317         x, y = self.empty[0]
318         if (self.matrix[y][x]):
319             self.empty[0] = (ex, ey)
320         else:
321             self.empty[1] = (ex, ey)
322
323 #-----------------------------------------
324
325 #global variables
326 #all end matrix
327 #all non-end matrix
328 #values for all end and non-end matrix
329 g_values = {}
330
331 #print ending count
332 end_count = 0
333 for matrix in all_ending_layouts():
334     end_count += 1
335     #check if this board has been touched
336     value = 0L
337     for t in matrix:
338         value = value << 3 | t
339     if g_values.has_key(value):
340         continue
341     rvalue = 0L
342     for i in range(5):
343         for j in range(4):
344             rvalue = rvalue << 3 | matrix[i*4 + 4-j-1]
345     layout = convert(matrix)
346     g_values[value] = rvalue
347     g_values[rvalue] = value
348     #start spawn
349     board = Board(layout)
350     board_pool = [board]
351     index = 0
352     while index < len(board_pool):
353         board_pool += board_pool[index].spawn()
354         index += 1
355     print len(g_values)
356
357 print "Total Endings count:", end_count
358 print "Total Layouts count:", len(g_values)
359
360 def solve_all_layouts():
361     g_nondups = {}
362     count = 0
363     from os import popen
364     outfile = open("input.log", "w+")
365     for value in g_values:
366         if count % 1000 == 0:
367             print count
368         if g_nondups.has_key(value):
369             continue
370         count += 1
371         rvalue = g_values[value]
372         g_nondups[value] = True
373         g_nondups[rvalue] = True
374         matrix = [0] * 20
375         val = value
376         for i in range(20):
377             matrix[20-i-1] = val & 7
378             val = val >> 3
379         layout = convert(matrix)
380         layout_str = "".join([str(i) for i in layout])
381         print >>outfile, layout_str, value, rvalue, layout
382     return count
383
384 count = solve_all_layouts()
385 print "Total Layouts count(no mirror):", count
386 print "Everything is over, see result.log for detailed result"