boxer.py推箱子暴力求解
公孙阳文
map.py
import numpy as np
class BoxMap:
def __init__(self, input, targets):
self.grids = np.array(input)
self.height = self.grids.shape[0]
self.width = self.grids.shape[1]
self.targets = targets
if self.is_end():
return
self.pos = self.get_pos()
self.feasible_region()
self.possible_act()
def get_pos(self):
it = np.nditer(self.grids, flags=['multi_index'])
while not it.finished:
if it[0] == 3:
return it.multi_index
it.iternext()
def is_empty(self, row, col):
if self.grids[row][col] == 0 or self.grids[row][col] == 3:
return True
else:
return False
def feasible_region(self):
self.fr = [self.pos]
row, col = self.pos
self.add_feasible(row, col)
def add_feasible(self, row, col):
neighbors = [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col)]
for neighbor in neighbors:
if self.is_empty(neighbor[0], neighbor[1]) and (neighbor[0], neighbor[1]) not in self.fr:
self.fr.append((neighbor[0], neighbor[1]))
self.add_feasible(neighbor[0], neighbor[1])
def get_box(self):
self.boxs = []
it = np.nditer(self.grids, flags=['multi_index'])
while not it.finished:
if it[0] == 2:
self.boxs.append(it.multi_index)
it.iternext()
def is_possible(self, row, col, move):
box_now = (row + move[0], col + move[1])
box_next = (row + 2 * move[0], col + 2 * move[1])
if self.grids[box_now[0]][box_now[1]] == 2 and self.grids[box_next[0]][box_next[1]] == 0:
return True
else:
return False
def possible_act(self):
self.pa = []
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for grid in self.fr:
for move in moves:
if self.is_possible(grid[0], grid[1], move):
self.pa.append((grid, move))
def is_end(self):
# print(self.grids)
for target in self.targets:
if self.grids[target[0]][target[1]] != 2:
self.end = False
return
self.end = True
if __name__ == '__main__':
input_map = [
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 2, 0, 0, 1],
[1, 0, 3, 2, 0, 0, 1],
[1, 0, 0, 2, 0, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1]
]
bm = BoxMap(input_map, [(1, 1), (2, 1), (3, 1)])
print(bm.pa)
StepTree.py
from map import BoxMap
import numpy as np
import copy
class Node:
# image = []
solution = []
def __init__(self, p, boxmap, action):
self.boxmap = boxmap
self.parent = p
self.action = action
self.history = []
self.childs = []
self.leaf = 0
if self.parent is None:
self.root = True
self.history.append(self.boxmap.grids)
self.pas = []
self.height = 0
else:
self.root = False
self.generate_steps()
self.height = self.parent.height + 1
def add_child(self, boxmap, pa):
self.childs.append(Node(self, boxmap, pa))
def next_map(self, pa):
pos, move = pa
now_grids = copy.copy(self.boxmap.grids)
now_grids[self.boxmap.pos[0]][self.boxmap.pos[1]] = 0
now_grids[pos[0] + move[0]][pos[1] + move[1]] = 3
now_grids[pos[0] + 2 * move[0]][pos[1] + 2 * move[1]] = 2
# print(now_grids)
return BoxMap(now_grids, self.boxmap.targets)
def generate_child(self):
if not self.boxmap.pa:
self.leaf = 1
for pa in self.boxmap.pa:
# print(pa)
self.add_child(self.next_map(pa), pa)
def generate_steps(self):
self.history = copy.copy(self.parent.history)
self.pas = copy.copy(self.parent.pas)
self.kill_node()
if self.leaf == 2:
self.history.append(self.boxmap.grids)
self.pas.append(self.action)
# Node.image.append(self.boxmap.grids)
if self.leaf == 0:
self.history.append(self.boxmap.grids)
self.pas.append(self.action)
# Node.image.append(self.boxmap.grids)
# self.generate_child()
def is_same_grids(self, comp_grids):
it = np.nditer(comp_grids, flags=['multi_index'])
while not it.finished:
if comp_grids[it.multi_index[0]][it.multi_index[1]] != self.boxmap.grids[it.multi_index[0]][
it.multi_index[1]]:
return False
it.iternext()
return True
def kill_node(self):
if self.boxmap.end:
self.leaf = 2
# print('end')
return
# for grids in Node.image:
# if self.is_same_grids(grids):
# self.leaf = 1
# # print('kill')
# return
for grids in self.history:
if self.is_same_grids(grids):
self.leaf = 1
# print('kill')
return
# print('continue')
def iter(node):
node.generate_child()
# print('height: ' + str(node.height)+ ' pas: ' +str(node.pas)+ ' leaf: ' +str(node.leaf))
for child in node.childs:
print('height: ' + str(child.height) + ' pas: ' + str(child.pas) + ' leaf: ' + str(child.leaf))
if child.leaf == 0:
iter(child)
if child.leaf == 1:
return
if child.leaf == 2:
Node.solution = child.history
return child.history
def logic_use(node):
# waiting for check
stack_list = []
# checked node
stack_list.append(node)
# while true
while len(stack_list) > 0:
# select one node from stack
point = stack_list[-1]
print('stack: ' + str(len(stack_list)) + ' height: ' + str(point.height) + ' pas: ' + str(point.pas) + ' leaf: ' + str(point.leaf))
# finish
if point.leaf == 2:
return point.history
# mark this node as checked
stack_list.pop()
# if node can bred
if point.leaf != 1:
point.generate_child()
for child in point.childs:
stack_list.append(child)
def choose_chapter(num):
if num == 70:
input_map = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 0, 2, 2, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 3, 1],
[1, 1, 1, 1, 1, 1, 1]
]
bm = BoxMap(input_map, [(4, 2), (4, 4)])
if num == 111:
input_map = [
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 2, 0, 0, 1],
[1, 0, 3, 2, 0, 0, 1],
[1, 0, 0, 2, 0, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1]
]
bm = BoxMap(input_map, [(1, 1), (2, 1), (3, 1)])
if num == 95:
input_map = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 2, 0, 2, 0, 1],
[1, 0, 0, 1, 2, 3, 1],
[1, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1]
]
bm = BoxMap(input_map, [(5, 1), (5, 2), (5, 3)])
if num == 98:
input_map = [
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 2, 0, 1],
[1, 1, 0, 2, 2, 3, 1],
[1, 1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1]
]
bm = BoxMap(input_map, [(2, 2), (1, 3), (2, 3)])
return bm
def main():
bm = choose_chapter(98)
start = Node(None, bm, None)
print(logic_use(start))
if __name__ == '__main__':
main()
类似资料：