import copy
import numpy as np
initState = input('输入初始8数码:')
initState='120345678'
tragetState = '012345678'
求逆序数
def nixishu(StrState):
toListState = list(StrState)
k = len(toListState)
number = 0
for i in range(1, k):
count = 0
for j in range(0, i):
if toListState[j] > toListState[i] : #列表调用使用中括号
count = count + 1
number = number + count
return number
#判断信号是否有解
def HaveSolution(initState1,tragetState1):
if nixishu(initState1)%2 == nixishu(tragetState1)%2:
return True
else:
return False
#打印信号是否有解
if HaveSolution(initState,tragetState):
print('有解')
else:
print('无解')
#将字符串转换为3*3的矩阵
def ToArray(strdata):
# strdata='012345678'
listdata=list(strdata)
arraydata = np.matrix(listdata)
arraydata_3=arraydata.reshape(3,3)
return arraydata_3
#找到0的位置
def getlocal(data):
i,j=np.where(data=='0')
return i[0],j[0]
#移动数字
def right(data):
i,j=getlocal(data)
arr=copy.deepcopy(data)
#只要0不在在矩阵的最右边,即不是data[i][2]即可以右移
if j in (0,len(data)-2):
data[i,j],data[i,j+1]=data[i,j+1], data[i,j] #交换元素
return arr
def left(data):
i,j=getlocal(data)
arr=copy.deepcopy(data)
#只要0不在在矩阵的最左边,即不是data[i][0]即可以左移
if j in (1,len(data)-1):
data[i,j],data[i,j-1]=data[i,j-1], data[i,j] #交换元素
return arr
def up(data):
i,j=getlocal(data)
arr=copy.deepcopy(data)
#只要0不在在矩阵的最上边,即不是data[0][j]即可以左移
if i in (1,len(data)-1):
data[i,j],data[i-1,j]=data[i-1,j], data[i,j] #同上一行交换元素
return arr
def down(data):
i,j=getlocal(data)
arr=copy.deepcopy(data)
#只要0不在在矩阵的最下边,即data[2][j]即可以左移(即0行和1行)
if i in (0,len(data)-2):
data[i,j],data[i+1,j]=data[i+1,j],data[i,j] #交换元素
return arr
class eightNumeber:
def init(self,data,parentflag):
self.data=data
self.parentflag=parentflag
# 实例类,将输入的3维元组/矩阵赋值给Node0
node0 = eightNumeber(ToArray(initState),'none')
openList=[ToArray(initState)]
closeList=[]
fuzhualist=[]
#宽度优先算法
while len(openList)>0:
fuzhualist=openList.pop(0)
# print(openList)
closeList.append(fuzhualist)
if np.all(fuzhualist==ToArray(tragetState)):
print('搜索完毕',fuzhualist)
# result=[]
# result.append(fuzhualist)
break
else:
getlocal(fuzhualist)
updata=up(fuzhualist)
# # # if np.all(updata !=ToArray(tragetState)):
if updata not in openList and updata not in closeList and updata is not None:
openList.append(updata)
print("上移 : ", updata)
downdata = down(fuzhualist)
if downdata not in openList and downdata not in closeList and downdata is not None:
openList.append(downdata)
print("下移 : ", downdata)
leftdata = left(fuzhualist)
if leftdata not in openList and leftdata not in closeList and leftdata is not None:
openList.append(leftdata)
print("下移 : ", leftdata)
rightdata = right(fuzhualist)
if rightdata not in openList and rightdata not in closeList and rightdata is not None:
openList.append(rightdata)
print("下移 : ", rightdata)
以上是源代码,其中leftdata not in closeList报错,但是fuzhualist not in closeList正确,且第一次循环中leftdata和fuzhualist完全相同
(判断矩阵元素是否列表中,报错)