Solution for 8 Puzzle

问题

八数码问题：在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。在本文中，我将展示如何编写一个程序，使用Python和PyGame以及A *算法解决八数码问题。

分析

由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

运行流程

要通过人工智能来解决这个问题，我们需要对如何获得目标节点有一个基本的了解。
以下是步骤：

1. 获取场景的当前状态（指现实世界中的棋盘或游戏）。

2. 找到可用的移动和他们的成本。

3. 选择成本最低的移动并将其设置为当前状态。

4. 检查它是否与目标状态匹配，如果是，则停止，如果没有移动到步骤1。

在代码中，程序将在一个状态中寻找一个0，然后寻找允许哪些移动并且花费最少。因此它将逐渐接近最终结果。

代码要求

Python3以上版本，PyGame库

1. Puzzle.py——实现A*算法
2. Puzzler.py——调用界面实现自动化解决八数码问题

源代码

puzzle.py

import math,random
class puzzle:
    def __init__(self):
        #self.node=[]
        self.fronts=[]
        self.GoalNode=['1','2','3','4','5','6','7','8','0']
        self.StartNode=['1','2','3','4','5','6','7','8','0']
        self.PreviousNode=[]
        self.prePreviousNode=[]
        self.PreviousCount=1
    
    def Solve(self):
        self.shufler(10)
        print(self.StartNode)
        self.sucessor(self.StartNode)
        nxNode=self.getNextNode()
        print (nxNode)
        count=1
        while nxNode!=self.GoalNode:
            #print(self.fronts)
            print(count)
            count+=1
            self.sucessor(nxNode)
            nxNode=self.getNextNode()
            print (nxNode)
        print('result',nxNode)
        
    
    def shufler(self):
                
            while True:
                node=self.StartNode
                subNode=[]
                direct=random.randint(1,4)
                getZeroLocation=node.index('0')+1
                subNode.extend(node)
                boundry=self.boundries(getZeroLocation)
                        
                if getZeroLocation+3<=9 and direct==1:
                    temp=subNode[node.index('0')]
                    subNode[node.index('0')]=subNode[node.index('0')+3]
                    subNode[node.index('0')+3]=temp
                    self.StartNode=subNode
                    return
                    
                elif getZeroLocation-3>=1 and direct==2:
                    temp=subNode[node.index('0')]
                    subNode[node.index('0')]=subNode[node.index('0')-3]
                    subNode[node.index('0')-3]=temp
                    self.StartNode=subNode
                    return
                
                elif getZeroLocation-1>=boundry[0] and direct==3:
                    temp=subNode[node.index('0')]
                    subNode[node.index('0')]=subNode[node.index('0')-1]
                    subNode[node.index('0')-1]=temp
                    self.StartNode=subNode
                    return
                
                elif getZeroLocation+1<=boundry[1] and direct==4:
                    temp=subNode[node.index('0')]
                    subNode[node.index('0')]=subNode[node.index('0')+1]
                    subNode[node.index('0')+1]=temp
                    self.StartNode=subNode
                    return
                
    def boundries(self,location):
        lst=[[1,2,3],[4,5,6],[7,8,9]]
        low=0
        high=0
        for i in lst:
            if location in i:
                low=i[0]
                high=i[2]
        
        return [low,high]
    
    def getNextNode(self):
        nxNode=[]
        tNode=[]
        while True:
            hrCost=100000
            for i in self.fronts:
                    if(i[-1]<hrCost):
                        hrCost=i[-1]
                        nxNode=i[0:-1]
                        tNode=i
            
            if tNode in self.PreviousNode and tNode in self.fronts:
                self.fronts.remove(tNode)
                self.PreviousNode.append(tNode)
                
            else:
                self.PreviousNode.append(tNode)
                return nxNode

    
    def heruistic(self,node):
        herMisplaced=0
        herDist=0
        
        for i in range(9):
            if node[i]!=self.GoalNode[i]:
                herMisplaced +=1
        for i in node:
            herDist +=math.fabs(node.index(i)-self.GoalNode.index(i))
        
        totalHerst=herDist+herMisplaced
       
        node.append(totalHerst)
        return node
        
        
    
    def sucessor(self,node=[]):
        subNode=[]
        getZeroLocation=node.index('0')+1
        subNode.extend(node)
        boundry=self.boundries(getZeroLocation)
#        for i in self.fronts:
#           if i[0:-1]==node:
#              self.fronts.remove(i)
        self.fronts=[]
                
        if getZeroLocation+3<=9:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')+3]
            subNode[node.index('0')+3]=temp
            self.fronts.append(self.heruistic(subNode))
            subNode=[]
            subNode.extend(node)
        if getZeroLocation-3>=1:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')-3]
            subNode[node.index('0')-3]=temp
            self.fronts.append(self.heruistic(subNode))
            subNode=[]
            subNode.extend(node)
        if getZeroLocation-1>=boundry[0]:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')-1]
            subNode[node.index('0')-1]=temp
            self.fronts.append(self.heruistic(subNode))
            subNode=[]
            subNode.extend(node)
        if getZeroLocation+1<=boundry[1]:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')+1]
            subNode[node.index('0')+1]=temp
            self.fronts.append(self.heruistic(subNode))
            subNode=[]
            subNode.extend(node)
        

puzzler.py

import pygame, sys, time
from pygame.locals import *
from puzzle import *

puzzle=puzzle()
#puzzle.Solve()

pygame.init()
WINDOWWIDTH = 300
WINDOWHEIGHT = 300
BASICFONT = pygame.font.Font('freesansbold.ttf',50)
windowSurface = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT), 0, 32)
pygame.display.set_caption('8 Puzzle')

BLACK = (96, 123, 139)
RED = (255, 0, 0)
GREEN = (255, 222, 173)
BLUE = (0, 0, 255)
WHITE=(255,255,255)
Text=(96, 123, 139)

blockTOP=0
blockLEFT=0
blocks=[]
blockNumber=1
#blocks.append({'rect':pygame.Rect(300, 80, 50, 100), 'color':RED, 'dir':})
for i in range(3):
    for j in range(3):
       
        if blockNumber>8:
            blocks.append({'rect':pygame.Rect(blockLEFT,blockTOP,99,99),'color':BLACK,'block':str(0)})
        else:
            blocks.append({'rect':pygame.Rect(blockLEFT,blockTOP,99,99),'color':GREEN,'block':str(blockNumber)})
        blockNumber+=1
        blockLEFT+=100
    blockTOP+=100
    blockLEFT=0

for b in blocks:        
        pygame.draw.rect(windowSurface, b['color'], b['rect'])
        textSurf = BASICFONT.render(b['block'], True,Text)
        textRect = textSurf.get_rect()
        textRect.center = b['rect'].left+50,b['rect'].top+50
        windowSurface.blit(textSurf, textRect)
pygame.display.update()
     
numShufles=50
evt=False  
while True:
    # check for the QUIT event
    for event in pygame.event.get():
        if event.type==MOUSEBUTTONDOWN and event.button==1:
            evt=True
            
    while numShufles>0:
        puzzle.shufler()
        puzzle.PreviousNode.extend(puzzle.StartNode)
        block=0
        for b in blocks:
            b['block']=str(puzzle.StartNode[block])
            block+=1
            
            if b['block']=='0':
                b['color']=BLACK
            else:
                b['color']=GREEN         
            pygame.draw.rect(windowSurface, b['color'], b['rect'])
            textSurf = BASICFONT.render(b['block'], True,Text)
            textRect = textSurf.get_rect()
            textRect.center = b['rect'].left+50,b['rect'].top+50
            windowSurface.blit(textSurf, textRect)
        pygame.display.update()
        time.sleep(0.04)
        numShufles-=1
        
        
    if evt==True:
            puzzle.sucessor(puzzle.StartNode)
            nxNode=puzzle.getNextNode()
            
            block=0
            for b in blocks:
                b['block']=str(nxNode[block])
                block+=1
                
                if b['block']=='0':
                    b['color']=BLACK
                else:
                    b['color']=GREEN         
                pygame.draw.rect(windowSurface, b['color'], b['rect'])
                textSurf = BASICFONT.render(b['block'], True,Text)
                textRect = textSurf.get_rect()
                textRect.center = b['rect'].left+50,b['rect'].top+50
                windowSurface.blit(textSurf, textRect)
            pygame.display.update()
            time.sleep(0.3)
            count=1
            
            while nxNode!=puzzle.GoalNode:
                #print(self.fronts)
                
                count+=1
                puzzle.sucessor(nxNode)
                nxNode=puzzle.getNextNode()
                block=0
                for b in blocks:
                    b['block']=str(nxNode[block])
                    block+=1
                    
                    if b['block']=='0':
                        b['color']=BLACK
                    else:
                        b['color']=GREEN         
                    pygame.draw.rect(windowSurface, b['color'], b['rect'])
                    textSurf = BASICFONT.render(b['block'], True,Text)
                    textRect = textSurf.get_rect()
                    textRect.center = b['rect'].left+50,b['rect'].top+50
                    windowSurface.blit(textSurf, textRect)
                pygame.display.update()
                time.sleep(0.03)
            break
                  
            
while True:
    # check for the QUIT event
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit() 

运行结果