八数码
Note：实现代码之前可以先写出伪代码，可以节省很多时间。编程语言只是一种实现工具。
def judge_position(init_m,target_m):#返回当前位置正确的数字的个数，以及0所在位置
current_right_nums=0 #store numbers of right position currently.
zero_r=0
zero_c=0
count=0 #当前状态中，各数字移动到正确位置的步数
for row in range(3):
for col in range(3):
if init_m[row][col]==0:
zero_r=row
zero_c=col
if init_m[row][col]==target_m[row][col]:
current_right_nums+=1
else:
for j in range(3):
for k in range(3):
if init_m[row][col]==target_m[j][k] and init_m[row][col]!=0:
count+=abs(row-j)+abs(col-k)
return (current_right_nums,zero_r,zero_c,count)
#----------------------------
def change_position(init_m,zero_r,zero_c):
#判断当前状态是否等于结束状态
current_right_nums,zero_r,zero_c,count=judge_position(init_m,target_matrix)
print("----------")
m1=[[i for i in row] for row in init_m]
m2=[[i for i in row] for row in init_m]
m3=[[i for i in row] for row in init_m]
m4=[[i for i in row] for row in init_m]
next_matrixes=[]
#交换位置：(zero_r+1,zero_c+1)(zero_r,zero_c-1)(zero_r,zero_c+1)(zero_r-1,zero_c)
if zero_r+1<3:
temp=m1[zero_r+1][zero_c]
m1[zero_r+1][zero_c]=m1[zero_r][zero_c]
m1[zero_r][zero_c]=temp
next_matrixes.append(m1)
if zero_c-1>-1: #zero_r,zero_c-1
temp=m2[zero_r][zero_c-1]
m2[zero_r][zero_c-1]=m2[zero_r][zero_c]
m2[zero_r][zero_c]=temp
next_matrixes.append(m2)
if zero_c+1<3: #(zero_r,zero_c+1)
temp=m3[zero_r][zero_c+1]
m3[zero_r][zero_c+1]=m3[zero_r][zero_c]
m3[zero_r][zero_c]=temp
next_matrixes.append(m3)
if zero_r-1>-1: #(zero_r-1,zero_c)
temp=m4[zero_r-1][zero_c]
m4[zero_r-1][zero_c]=m4[zero_r][zero_c]
m4[zero_r][zero_c]=temp
next_matrixes.append(m4)
#判断每一状态中，各数字移动到正确位置的补步数，选取最小的
matrixes_info=[]
for martrix in next_matrixes:
matrixes_info.append(list(judge_position(martrix,target_matrix)))
to_target_counts=[i[3] for i in matrixes_info]
best_matrix=next_matrixes[to_target_counts.index(min(to_target_counts))]
if matrixes_info[next_matrixes.index(best_matrix)][3]==0:
print("\nSuccess!Next step is target matrix:")
for row in best_matrix:
print(row)
return
print("next_step:")
for row in best_matrix:
print(row)
print("Current_right_numbers:",matrixes_info[next_matrixes.index(best_matrix)][0])
print("To target need steps:",matrixes_info[next_matrixes.index(best_matrix)][3])
zero_r=matrixes_info[next_matrixes.index(best_matrix)][1]
zero_c=matrixes_info[next_matrixes.index(best_matrix)][2]
change_position(best_matrix,zero_r,zero_c)
def regular_matrix(init_m,target_m):
current_right_nums,zero_r,zero_c,count=judge_position(init_matrix,target_matrix)
change_position(init_m,zero_r,zero_c)
if __name__ == "__main__":
init_matrix=[[2,8,3],[1,0,4],[7,6,5]]
target_matrix=[[1,2,3],[8,0,4],[7,6,5]]
current_right_nums,zero_r,zero_c,count=judge_position(init_matrix,target_matrix)
regular_matrix(init_matrix,target_matrix)
