python华容道最短路径_Python方法生成华容道所有开局

玩蛇网本文是关于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,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"

玩蛇网文章，转载请注明出处和文章网址：https://www.iplaypy.com/code/game/g2611.html

相关文章 Recommend