Python方法生成华容道所有开局，python华容道开局,编橙之家本文是关于Pyt

Python方法生成华容道所有开局，python华容道开局,编橙之家本文是关于Pyt

编橙之家本文是关于Python语言解决游戏算法的相关文章。Python方法生成华容道所有求解的开局，其中含镜像263977种，不含镜像132156种。

华容道所有开局求解的思路是:
1. 生成所有终局
2. 广度优先推出所有开局，形成一个树
3. 树中所有的节点都是开局，可以根据Level进行排序

#! /usr/bin/env python# -*- coding: utf-8 -*-#-----------www.iplaypy.com----------------------------#  Definitions#    B(4): Box, 2x2#    V(2): Vertical Bar, 1x2#    H(3): Horizontal Bar, 2x1#    D(1): Dot, 1x1#    E(0): the empty 1x1(or space)#    U(7): undefined, or (?)Empty,Dot,Vbar,Hbar,Box,Undef = 0,1,2,3,4,7row, 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    printdef all_ending_layouts():    """Check all possible configurations when CaoCao is at the exit."""    values = {}    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):                    value = 0L                    for t in layout:                        value = value << 3 | t                    if not values.has_key(value):                        rvalue = 0L                        for i in range(5):                            for j in range(4):                                rvalue = rvalue << 3 | layout[i*4 + 4-j-1]                        values[value] = True                        values[rvalue] = True                        yield layoutdef 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 0def 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 []#---------------------------------------------------------------# spawn all the layouts to be solved#convert 4*5 DHVB into block layouts(totally 10 blocks)def convert(matrix):    b = [0, 0, 0, 0]    c,d = 0,0    result = []    for i in range(20):        x = i % 4        y = i / 4        n = matrix[i]        if n == Dot:            result += [1, x, y]        elif n == Vbar:            if y == 0 or b[x] == 0:                b[x] = 2                result += [2, x, y]            else:                b[x] = 0        elif n == Hbar:            if c == 0:                result += [3, x, y]                c = 3            else:                c = 0        elif n == Box:            if d % 4 == 0:                result += [4, x, y]                d = 1            else:                d += 1    return resultfrom copy import deepcopyclass Board:    def __init__(self, layout):        #the moved index to generate this board        self.moved = -1        #init the matrix and items        self.items = [()] * 10 #BIT:type:3,x:2,y:3), x,y is zero-based        self.empty = [(0,0), (0,0)] #2 empty slot's position in matrix, (col, row)        #-1 mean's boundary        f = -1        #[1+5+1][1+4+1] of byte, each byte is the (index+1) in items        #  the extra 1s is for the boundary        self.matrix = [ [f, f, f, f, f, f],                        [f, 0, 0, 0, 0, f],                        [f, 0, 0, 0, 0, f],                        [f, 0, 0, 0, 0, f],                        [f, 0, 0, 0, 0, f],                        [f, 0, 0, 0, 0, f],                        [f, f, f, f, f, f] ]        #calculate the items into cell-matrix        type, x, y = 0, 0, 0        for i in range(10):            type = layout[i*3]            x = layout[i*3+1]            y = layout[i*3+2]            self.items[i] = (type, x, y)            self.matrix[y+1][x+1] = i+1            if type == Vbar:                self.matrix[y+2][x+1] = i+1            elif type == Hbar:                self.matrix[y+1][x+2] = i+1            elif type == Box:                self.matrix[y+1][x+2] = i+1                self.matrix[y+2][x+1] = i+1                self.matrix[y+2][x+2] = i+1        #find out the empty blocks        count = 0        for i in range(7):            for j in range(6):                if not self.matrix[i][j]:                    self.empty[count] = (j, i)                    if not count: count += 1                    else: return    def getValue(self):        val, bt = 0L, 0        for i in range(1, 6):            for k in range(1, 5):                index = self.matrix[i][k] - 1                if index < 0: bt = 0                else: bt = self.items[index][0]                val = val << 3 | bt        return val    def getRValue(self):        val, bt = 0L, 0        for i in range(1, 6):            for k in range(4, 0, -1):                index = self.matrix[i][k] - 1                if index < 0: bt = 0                else: bt = self.items[index][0]                val = val << 3 | bt        return val    #spawn new Board by moving the cells around empty cells    #  changes global variable: g_values    def spawn(self):        global g_values        new_boards = []        #collect the cells around empty cells        around = [0] * 8        #DO NOT change the order of ulrd, it's been depended        #       ulrd: Up/Left/Right/Down        ulrd = ((0,-1), (-1,0), (1,0), (0,1))        for e in self.empty: #two empty blocks, always 2            x, y = e            for k in range(4):                dir = ulrd[k]                nx = x + dir[0]                ny = y + dir[1]1c40                index = self.matrix[ny][nx] - 1                if index >= 0:                    newb = deepcopy(self)                    newb.moved = index                    if newb.tryAndMove(index, -dir[0], -dir[1]):                        value = newb.getValue()                        if not g_values.has_key(value):                            if len(g_values) % 1000 == 0:                                print len(g_values)                            rvalue = newb.getRValue()                            g_values[value] = rvalue                            g_values[rvalue] = value                            new_boards.append(newb)        return new_boards    def tryAndMove(self, index, dx, dy):        item = self.items[index]        type, x, y = item        ret = False        #ci is short for cell index        ci1 = ci2 = ci3 = ci4 = 0        if type == Dot:            ci1 = self.matrix[y+dy+1][x+dx+1]            ret = not ci1 or ci1 == index+1            if ret:                self.matrix[y+1][x+1] = 0                self.matrix[y+dy+1][x+dx+1] = index + 1                self.items[index] = (type, x+dx, y+dy)                self.setEmpty(x+1, y+1)        elif type == Vbar:                ci1 = self.matrix[y+dy+1][x+dx+1]                ci2 = self.matrix[y+dy+2][x+dx+1]                ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1)                if ret:                    self.matrix[y+1][x+1] = 0                    self.matrix[y+2][x+1] = 0                    self.matrix[y+dy+1][x+dx+1] = index + 1                    self.matrix[y+dy+2][x+dx+1] = index + 1                    self.items[index] = (type, x+dx, y+dy)                    if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)                    if self.matrix[y+2][x+1] == 0: self.setEmpty(x+1, y+2)        elif type == Hbar:                ci1 = self.matrix[y+dy+1][x+dx+1]                ci2 = self.matrix[y+dy+1][x+dx+2]                ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1)                if ret:                    self.matrix[y+1][x+1] = 0                    self.matrix[y+1][x+2] = 0                    self.matrix[y+dy+1][x+dx+1] = index + 1                    self.matrix[y+dy+1][x+dx+2] = index + 1                    self.items[index] = (type, x+dx, y+dy)                    if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)                    if self.matrix[y+1][x+2] == 0: self.setEmpty(x+2, y+1)        elif type == Box:                ci1 = self.matrix[y+dy+1][x+dx+1]                ci2 = self.matrix[y+dy+1][x+dx+2]                ci3 = self.matrix[y+dy+2][x+dx+1]                ci4 = self.matrix[y+dy+2][x+dx+2]                ret = (not ci1 or ci1==index+1) and (not ci2 or ci2==index+1) and \                      (not ci3 or ci3==index+1) and (not ci4 or ci4==index+1)                if ret:                    self.matrix[y+1][x+1] = 0                    self.matrix[y+1][x+2] = 0                    self.matrix[y+2][x+1] = 0                    self.matrix[y+2][x+2] = 0                    self.matrix[y+dy+1][x+dx+1] = index+1                    self.matrix[y+dy+1][x+dx+2] = index+1                    self.matrix[y+dy+2][x+dx+1] = index+1                    self.matrix[y+dy+2][x+dx+2] = index+1                    self.items[index] = (type, x+dx, y+dy)                    if self.matrix[y+1][x+1] == 0: self.setEmpty(x+1, y+1)                    if self.matrix[y+1][x+2] == 0: self.setEmpty(x+2, y+1)                    if self.matrix[y+2][x+1] == 0: self.setEmpty(x+1, y+2)                    if self.matrix[y+2][x+2] == 0: self.setEmpty(x+2, y+2)        return ret    def setEmpty(self, ex, ey):        x, y = self.empty[0]        if (self.matrix[y][x]):            self.empty[0] = (ex, ey)        else:            self.empty[1] = (ex, ey)#-----------------------------------------#global variables#all end matrix#all non-end matrix#values for all end and non-end matrixg_values = {}#print ending countend_count = 0for matrix in all_ending_layouts():    end_count += 1    #check if this board has been touched    value = 0L    for t in matrix:        value = value << 3 | t    if g_values.has_key(value):        continue    rvalue = 0L    for i in range(5):        for j in range(4):            rvalue = rvalue << 3 | matrix[i*4 + 4-j-1]    layout = convert(matrix)    g_values[value] = rvalue    g_values[rvalue] = value    #start spawn    board = Board(layout)    board_pool = [board]    index = 0    while index < len(board_pool):        board_pool += board_pool[index].spawn()        index += 1    print len(g_values)print "Total Endings count:", end_countprint "Total Layouts count:", len(g_values)def solve_all_layouts():    g_nondups = {}    count = 0    from os import popen    outfile = open("input.log", "w+")    for value in g_values:        if count % 1000 == 0:            print count        if g_nondups.has_key(value):            continue        count += 1        rvalue = g_values[value]        g_nondups[value] = True        g_nondups[rvalue] = True        matrix = [0] * 20        val = value        for i in range(20):            matrix[20-i-1] = val & 7            val = val >> 3        layout = convert(matrix)        layout_str = "".join([str(i) for i in layout])        print >>outfile, layout_str, value, rvalue, layout    return countcount = solve_all_layouts()print "Total Layouts count(no mirror):", countprint "Everything is over, see result.log for detailed result"

编橙之家文章，