|
- ################################################################################################################其他函数##
- import numpy as np
- from Classes import Klotski
- from Classes import Node
- from Classes import LinkedList
- import copy
- import random
-
- def Simplify_layers(link_refer, link):
- link1_point = link_refer.head
- link.point = link.head
- if link.size > 0:
- while link1_point is not None:
- while link.point is not None:
- if np.array_equal(link1_point.Data.map, link.point.Data.map) or \
- np.array_equal(link1_point.Data.map, np.fliplr(link.point.Data.map)):
- link.delete_point()
-
- if link.point is not None:
- link.point = link.point.next
- link1_point = link1_point.next
- link.point = link.head
- link.point = link.head
- return link
-
-
-
- def Simplify_layer(link):
- node = link.head
- link.point = link.head
- while node != None:
- link.point = node.next
- while link.point != None:
- if np.array_equal(link.point.Data.map,node.Data.map) or \
- np.array_equal(link.point.Data.map, np.fliplr(node.Data.map)):
- link.delete_point()
- else:
- link.point = link.point.next
- node = node.next
- link.point = link.head
- return link
-
-
- def SolveMethodTable(table):
- strategy = LinkedList()
- table.index = table.head
- while table.index != None and table.index.Data.point.Value > 0:
- node = table.index.Data.point
- nodeTemp = Node(node.Data)
- nodeTemp.Action = node.Action
- strategy.insert(nodeTemp)
- if table.index.Data.point.Data.x[0] == table.head.Data.head.Data.map.shape[0]-1 and table.index.Data.point.Data.y[0] == table.head.Data.head.Data.map.shape[1]/2:
- break
- table.index = table.index.next
- strategy.GetOrder()
- temp=[]###有没有问题?
- i = 1
- strategy.point = strategy.head
- strategy.point.Action = [0,'None']
- strategy.point=strategy.point.next
- while strategy.point != None:
- if temp == strategy.point.prev.Action[0]:
- print(' ',strategy.point.Action[1], end="")
- if strategy.point.next != None and strategy.point.Action[0] != strategy.point.next.Action[0]:
- print('\n', strategy.point.Data.map)
- strategy.point=strategy.point.next
- if strategy.point != None:
- temp=strategy.point.Action[0]
- continue
- print('\n 第', i, '步 :', '%d' % strategy.point.Action[0], strategy.point.Action[1], end="")
- i=i+1
- if strategy.point.next != None and strategy.point.Action[0] != strategy.point.next.Action[0]:
- print('\n', strategy.point.Data.map)
- strategy.point = strategy.point.next
- if strategy.point != None:
- temp=strategy.point.Action[0]
- print('\n', strategy.tail.Data.map,end="")
- strategy.point = strategy.head
- return strategy
-
- def SameJudge(link1,link2):
- flag = 'N'
- order1 = 0
- order2 = 0
- link1.point = link1.head
- link2.point = link2.head
- if link2.size>0:
- while link1.point != None:
- while link2.point != None :
- if np.array_equal(link1.point.Data.map,link2.point.Data.map):
- order1 = link1.point.Order
- order2 = link2.point.Order
- flag = 'Y'
- break
- if link2.point != None:
- link2.point =link2.point.next
- link1.point = link1.point.next
- link2.point = link2.head
- return flag,order1,order2
- def Generate_One_bfs(klotski, layer, needle):
- caoMove = 0
- order = 1
- if layer is None:
- layer = 0
- layer = layer+1
- link2 = LinkedList()
- for i in range(1, len(klotski.x)+1):
- for j in range(1, 9):
- if j == 1:
- action = 'UP'
- elif j == 2:
- action = 'DOWN'
- elif j == 3:
- action = 'LEFT'
- elif j == 4:
- action = 'RIGHT'
- elif j == 5:
- action = 'D_UP'
- elif j == 6:
- action = 'D_DOWN'
- elif j == 7:
- action = 'D_LEFT'
- elif j == 8:
- action = 'D_RIGHT'
- [move, klotski1] = klotski.move(i, action)
- if move == 'Y':
- node = Node(klotski1)
- link2.insert(node)
- link2.tail.Layer = layer
- link2.tail.Rel = needle
- link2.tail.Order = order
- order = order+1
- link2.tail.Action = [i, action]
- # if i == 1 and link2.head is not None and link2.tail.Data.x[0] == klotski.map.shape[0]-1 and link2.tail.Data.y[0] == klotski.map.shape[1]/2:
- # caoMove = 100
- if i == 1:
- while link2.point is not None:
- if link2.point.Data.x[0] == klotski.map.shape[0] - 1 and link2.point.Data.y[0] == klotski.map.shape[1] / 2:
- caoMove = 100
- # link2.point = link2.head
- # return link2, caoMove
- link2.point = link2.point.next
- link2.point = link2.head
- return link2, caoMove
-
- # 进行一个节点的子节点进行展开
- def Generate_One(klotski, layer, needle, simulation = -1):
- caoMove = 0
- order = 1
- if layer is None:
- layer = 0
- layer = layer+1
- link2 = LinkedList()
- for i in range(1, len(klotski.x)+1):
- for j in range(1, 9):
- if j == 1:
- action = 'UP'
- elif j == 2:
- action = 'DOWN'
- elif j == 3:
- action = 'LEFT'
- elif j == 4:
- action = 'RIGHT'
- elif j == 5:
- action = 'D_UP'
- elif j == 6:
- action = 'D_DOWN'
- elif j == 7:
- action = 'D_LEFT'
- elif j == 8:
- action = 'D_RIGHT'
- [move, klotski1] = klotski.move(i, action)
- if move == 'Y':
- node = Node(klotski1)
- link2.insert(node)
- link2.tail.Layer = layer
- link2.tail.Rel = needle
- link2.tail.Order = order
- order = order+1
- link2.tail.Action = [i, action]
- # if simulation == 0 and i == 1:
- # caoMove = 'Y'
- if simulation == -1:
- if i == 1:
- while link2.point is not None:
- if link2.point.Data.x[0] == klotski.map.shape[0]-1 and link2.point.Data.y[0] == klotski.map.shape[1]/2:
- caoMove = 100
- return link2, caoMove
- elif link2.point.Action[1] == 'DOWN':
- caoMove = 1
- link2.point.Value = link2.point.Value + 2*link2.point.Data.x[0]
- else:
- caoMove = 2
- link2.point.Value = link2.point.Value + 0.5*link2.point.Data.x[0]
- link2.point = link2.point.next
- link2.point = link2.head
- elif simulation == 1:
- if i == 1:
- while link2.point is not None:
- if link2.point.Data.x[0] == klotski.map.shape[0]-1 and link2.point.Data.y[0] == klotski.map.shape[1]/2 :
- caoMove = 100
- return link2, caoMove
- link2.point = link2.point.next
- return link2, caoMove
-
-
- # 针对一层的节点进行儿子节点的展开
- def Generate_Layers(link1):
- caoMove = 0
- link2 = LinkedList()
- if link1.size > 0:
- link1_size = link1.size
- link1.point = link1.head
- for i in range(link1_size):
- needle = link1.point.Order
- klotski = link1.point.Data
- # 调用Generate_One函数
- [link_One, caoMove] = Generate_One_bfs(klotski, link1.tail.Layer, needle)
- link2 = link2.connect(link_One, caoMove)
- link1.point = link1.point.next
- if caoMove == 100:
- break
- return link2, caoMove
-
- def finalStateSuppose(klotski,level):
- link_end = LinkedList()
- # num2 = length(find(klotski.h[2:6] == 2))
- num2 = len(np.where(klotski.h[1:6] == 2)[0])
- klotski_end = Klotski(0)
- klotski_end.w = klotski.w
- klotski_end.h = klotski.h
- if num2 % 2 == 1:
- # 部分默认
- # 默认4为横列
- klotski_end.x = np.array([4, 0,0,0,0, 3,4,5,3,3])
- klotski_end.y = np.array([2, 0,0,0,0, 1,1,1,3,4])
- # 奇数个heng
- if level == 1:
- klotski_end.x[1:5] = [1,1,1,1]
- klotski_end.y[1:5] = [1,2,3,4]
- klotski_end.getmap()
- node = Node(klotski_end)
- link_end. insert(node)
- elif level == 3:
- klotski_end.x[1:5] = [1,2,1,1]
- klotski_end.y[1:5] = [1,1,3,4]
- link_end = StateSuppose_h4(link_end,klotski_end,level)
- klotski_end.x = np.array([4, 1,2,1,1, 3,4,5,3,3])
- klotski_end.y = np.array([2, 3,3,1,2, 1,1,1,3,4])
- link_end = StateSuppose_h4(link_end,klotski_end,level)
- elif level == 5:
- klotski_end.x[1:5] = [1,1,2,2]
- klotski_end.y[1:5] = [1,3,1,3]
- link_end = StateSuppose_h4(link_end,klotski_end,level)
- else:
- # 偶数个横
- # 默认4为竖列
- klotski_end.x = np.array([4, 0,0,0,0, 3,4,5,1,2])
- klotski_end.y = np.array([2, 0,0,0,0, 1,1,1,1,1] )
- if level == 2:
- klotski_end.x[1:5] = [3,1,1,1]
- klotski_end.y[1:5] = [3,2,3,4]
- link_end = StateSuppose_s4(link_end,klotski_end,level)
- klotski_end.x = np.array([4, 1,1,1,2, 3,4,5,2,3])
- klotski_end.y = np.array([2, 3,1,2,3, 1,1,1,4,4])
- link_end = StateSuppose_s4(link_end,klotski_end,level)
- elif level == 4:
- klotski_end.x[1:5] = [1,2,3,1]
- klotski_end.y[1:5] = [3,3,3,2]
- link_end = StateSuppose_s4(link_end,klotski_end,level)
- klotski_end.x = np.array([4, 3,1,2,1, 3,4,5,1,2])
- klotski_end.y = np.array([2, 3,1,1,3, 1,1,1,4,4])
- link_end = StateSuppose_s4(link_end,klotski_end,level)
- klotski_end.x = np.array([4, 1,1,2,2, 3,4,5,2,3])
- klotski_end.y = np.array([2, 1,3,1,3, 1,1,1,4,4])
- link_end = StateSuppose_s4(link_end,klotski_end,level)
-
- for i in range(1,link_end.size):
- link_end.point.Layer = 1
- link_end.point.Order = i
- link_end.point = link_end.point.next
- return link_end
-
- def StateSuppose_h4(link_end,klotski_end,level):
- klotski_end.getmap()
- node = Node(klotski_end)
- link_end.insert(node)
- for i in range(1,level):
- klotski_end = copy.deepcopy(klotski_end) #改变对象的地址
- klotski_end.x[[i, 8]] = klotski_end.x[[8, i]]
- klotski_end.y[[i, 8]] = klotski_end.y[[8, i]]
- klotski_end.x[9] = klotski_end.x[8]
- klotski_end.y[9] = klotski_end.y[8] + 1
- klotski_end.getmap()
- node = Node(klotski_end)
- link_end.insert(node)
- return link_end
-
- def StateSuppose_s4(link_end,klotski_end,level):
- klotski_end.getmap()
- node = Node(klotski_end)
- link_end.insert(node)
- for i in range(1,5-level+1):
- klotski_end = copy.deepcopy(klotski_end) #改变对象的地址
- klotski_end.x[[level+i-1, 8]] = klotski_end.x[[8, level+i-1]]
- klotski_end.y[[level+i-1, 8]] = klotski_end.y[[8, level+i-1]]
- klotski_end.x[9] = klotski_end.x[8]+ 1
- klotski_end.y[9] = klotski_end.y[8]
- klotski_end.getmap()
- node = Node(klotski_end)
- link_end.insert(node)
- return link_end
-
- def randomfSS(klotski):
- link_end = LinkedList()
- klotski_end = Klotski(0)
- location = []
- rows = klotski.map.shape[0]
- column = klotski.map.shape[1]
- board = np.zeros((rows, column))
- board[rows-2:rows, column//2-1:column//2+1] = 1
- location.append((rows-1, column//2))
- for q in range(1, 11):
- for r in range(1, len(klotski.x)):
- klotski_end = copy.deepcopy(klotski_end)
- h, l = klotski.w[r], klotski.h[r]
- if h == 2:
- if l == 1:
- sign = 2
- if l == 2:
- sign = 1
- else:
- if l == 1:
- sign = 4
- if l == 2:
- sign = 3
- while True:
- x, y = random.randint(0, rows - h), random.randint(0, column - l)
- if all(board[x + i][y + j] == 0 for j in range(l) for i in range(h)):
- location.append((x + 1, y + 1))
- for i in range(h):
- for j in range(l):
- board[x + i][y + j] = sign
- break
-
- klotski_end.x, klotski_end.y = [t[0] for t in location], [t[1] for t in location]
- link_end.insert(klotski_end)
- for i in range(1,link_end.size):
- link_end.point.Layer = 1
- link_end.point.Order = i
- link_end.point = link_end.point.next
|