八数码问题（8皇后问题）的A*算法求解（Python实现）

# -*-coding:utf-8 -*- # HUAWEI Harmony OS Editor # @Author: Guokai Zhang 2020214266 # @Development time:2022/11/10 9:45 # @File: A_star.py # @Software: PyCharm from tkinter import * import tkinter.messagebox as messagebox from datetime import datetime class GUI: def __init__(self): self.window=Tk() self.window.geometry('720x680') self.window.title('八数码迷宫模拟器') self.v1=StringVar() self.v1.set('') self.v2=IntVar() self.v2.set(0) self.Solution=Solution() frame=Frame(self.window) frame1 = Frame(self.window) frame.pack() frame1.pack() welcome=Label(frame,text='八数码迷宫模拟器',font=('黑体',20),anchor='center',bg='red') please_input = Label(frame1, text='·请输入起始八数码：', font=('黑体', 13), anchor='n') input = Entry(frame1, textvariable=self.v1, justify=LEFT, width=25, font=('宋体', 13)) execute_Button = Button(frame1, text='开始', font=('黑体', 15), command=self.printWords) exit_Button = Button(frame1, text='退出', font=('黑体', 15), command=exit) words_output = Label(frame1, text='以下为生成结果：', font=('黑体', 13)) self.result_print = Text(frame1, font=('楷体,16'), width=50, height=25) welcome.grid() please_input.grid(row=1,column=0) input.grid(row=2) execute_Button.grid(row=3,column=1) exit_Button.grid(row=3,column=2) words_output.grid(row=4) self.result_print.grid() self.window.mainloop() def exit(self): exit(0) # self.result_print.insert(INSERT, result[0:-1]) def timer(self): starttime = self.Solution.starttime return starttime def printWords(self): if self.v1=='': messagebox.showinfo('Error', '请输入起始八数码！') else: result=self.Solution.salvePuzzle(self.v1.get(),'012345678') endtime=datetime.now() result1=result[0:-1] result1.reverse() for each in result1: self.result_print.insert(INSERT, each[0:3]+'\n') self.result_print.insert(INSERT, each[3:6]+'\n') self.result_print.insert(INSERT, each[6:] + '\n'+'\n') self.result_print.insert(INSERT, '012' + '\n') self.result_print.insert(INSERT, '345' + '\n') self.result_print.insert(INSERT, '678' + '\n' + '\n') self.result_print.insert(INSERT, '路径长度为：') self.result_print.insert(INSERT, result[-1]) self.result_print.insert(INSERT, '搜索时间为：') self.result_print.insert(INSERT, endtime-self.timer()) class Solution: starttime = datetime.now() def salvePuzzle(self, init, targ): start_form=init#起始八位码 end_form=targ# 目标八位码 openlist=[]# open表 closelist=[]#close表 hx=self.calcDistH(start_form,end_form)#h(n) # index：表内索引 node_form：八位码 fat:父亲指针 gn:g(n)深度 hn:h(n) step：移动方向 node_trait={'index':0,'node_form':init,'fat_Ana':-1,'gn':0,'hn':hx,'step':''} best_forms_List=[] movelist = [] # 存储移动记录(uldr) def findBest(openlist): bestnode=openlist[0] count=-1#open表内索引 index=0#返回索引 fn = openlist[0]['gn'] + openlist[0]['hn'] for each in openlist: count=count+1 if each['gn']+each['hn']<fn: fn=each['gn']+each['hn'] bestnode=each index=count return bestnode,index def findFather(closelist,index): for each in closelist: if each['index']==index: return each def check(closelist,cur_form): count=-1 for node in closelist: count=count+1 if node['node_form']==cur_form: return count return -1 best_node = {} # 最佳节点 best_form = '' # 最佳节点的八位码 # 开始函数主体 openlist.append(node_trait) index_init=0#初始index ana=0 while ana<100000: best_node,index=findBest(openlist)#最优节点 best_form=best_node['node_form']# 最优八数码 if best_form==end_form:#若当前步找到的最优节点为目标点 持续寻找其父亲节点 直到找到初始状态 while True: father_index=best_node['fat_Ana'] movelist.append(best_node['step']) if father_index==-1: break best_node=findFather(closelist,father_index) best_forms_List.append(best_node['node_form']) if movelist!=[]: break #当前最优节点不是目标终点 将最优节点从open表剔除，加入close表，对该节点进行拓展，将拓展临近节点加入open表 del openlist[index_init] closelist.append(best_node) # 上下左右 寻找拓展方式 step_choose=['u','d','l','r']#四种走法 for step in step_choose: index_0 = best_form.find('0')#八数码中0位置索引 Z_row=index_0//3#横坐标 Z_col=index_0%3 #纵坐标 if step == 'u': Z_row=Z_row-1 if step == 'd': Z_row=Z_row+1 if step == 'l': Z_col=Z_col-1 if step == 'r': Z_col=Z_col+1 if Z_col<0 or Z_col>2 or Z_row<0 or Z_row>2: continue #若移动后跃出九宫格 舍去 cur_index0=Z_row*3+Z_col#移动后的0索引 near_form=self.moveMap(best_form,index_0,cur_index0)#临近节点的八数码 node_trait_temp = {'index': 0, 'node_form': '', 'fat_Ana': best_node['index'], 'gn': best_node['gn'] + 1, 'hn': hx, 'step': ''} node_trait_temp['fat_Ana']=best_node['index']#父亲指针指向bestnode node_trait_temp['step']=step#记录移动方式 #node_trait_temp['gn']=best_node['gn']+1#gn深度++ nearindex=check(closelist,near_form) if nearindex!=-1: continue nearindex = check(openlist, near_form) if nearindex != -1: continue near_hn=self.calcDistH(near_form,end_form) #计算临近节点的h(n) ana=ana+1 node_trait_temp['index']=ana node_trait_temp['hn']=near_hn node_trait_temp['node_form']=near_form openlist.append(node_trait_temp) movelist.reverse() best_forms_List.append(len(movelist)) return best_forms_List def calcDistH(self, src_map, dest_map): sum = 0 for i in range(9): if src_map[i] == '0': continue for j in range(9): if src_map[i] == dest_map[j]: val = abs(i - j) sum = sum + val break return sum def moveMap(self, cur_map, i, j): temp=cur_map[j] trailer = cur_map[j+1:] if j+1<len(cur_map) else '' cur_map=cur_map[0:j]+cur_map[i]+trailer cur_map=cur_map[0:i]+