玩蛇网提供最新Python编程技术信息以及Python资源下载!

Python方法生成华容道所有开局

python 培训

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

python 华容道游戏

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

#! /usr/bin/env python
# -*- coding: utf-8 -*-

#-----------www.iplaypython.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,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."""
    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 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 []

#---------------------------------------------------------------
# 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 result

from copy import deepcopy

class 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 matrix
g_values = {}

#print ending count
end_count = 0
for 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_count
print "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 count

count = solve_all_layouts()
print "Total Layouts count(no mirror):", count
print "Everything is over, see result.log for detailed result"


玩蛇网原创,转载请注明文章出处和来源网址:http://www.iplaypython.com/code/game/g2611.html



微信公众号搜索"玩蛇网Python之家"加关注,每日最新的Python资讯、图文视频教程可以让你一手全掌握。强烈推荐关注!

微信扫描下图可直接关注

玩蛇网Python新手QQ群,欢迎加入: ① 240764603 玩蛇网Python新手群
文章发布日期:2016-04-01 09:10 玩蛇网 www.iplaypython.com

评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
相关文章推荐
别人正在看
特别推荐
去顶部去底部