Eight Puzzle Python Find Solution Self Init_state
- Download astart8puzzle.zip - 2.4 KB
Introduction
8-Puzzle is an interesting game which requires a player to move blocks one at a time to solve a picture or a particular pattern. In this article I will be showing you how to write an intelligent program that could solve 8-Puzzle automatically using the A* algorithm using Python and PyGame. Instead of a picture, we will use a pattern of numbers as shown in the figure, that is the final state. If you need to go through the A* algorithm theory or 8-Puzzle, just wiki it.
Background
Artificial Intelligence is the science of making a machine intelligent. To make a machine intelligent we need some way of processing the data and environment. Everything in AI follows an algorithm. At the basic level, there are simple but impressive algorithms. A* algorithm is one of the basic algorithms of AI. A* employs a heuristic function to find the solution to a problem. For more info on AI and its algorithms, get the book "Artificial Intelligence: A Modern Approach".
Basic Workflow
Solving 8-Puzzle manually varies from person to person. To solve it by computer or AI, we need a bit of a basic understanding of how it works to get the Goal node.
Following are the steps:
- Get the current state of the scenario (refers to the board or game in real world).
- Find the available moves and their cost.
- Choose the move with the least cost and set it as the current state.
- Check if it matches the goal state, if yes terminate, if no move to step 1.
In the code, our agent (program) will look for an empty space ('0') in a state and then which moves are allowed and have the least cost. As a result it will move towards the goal which is our final state.
Using the code
First you will need Python version 3.2 and a compatible PyGame library. There are two classes.
- A* implementation (py8puzzle.py).
- Simulation (requires PyGame) (puzzler.py).
The A* algorithm class is independent. You can use it to write a piece of code that will not require pyGame or you can import it to another project. The simulation file is a small game written in PyGame to solve the scenario. Your interaction will be minimal. Just run the file (puzzler.py). It will generate a random scenario, then just click any where in the window and the program will attempt to solve it. As this is an AI problem, expect some worst scenario to take a bit of a long time. Generally it takes less than a minute.
py8puzzle.py
Let's take a look at the code.
First initialize the environment using the constructors:
import math,random class puzzel: 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=[]
As you can see, the start and goal nodes are the same, also they are one dimensional. We will use the start node to create the scenario to be solved. This is because there are a lot of scenarios which are unsolvable. Instead of using a two dimensional array I am using one dimension only. In the code, I am processing it in such a way that it will do the same thing. '0' indicates empty space.
To generate the scenario:
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
Heuristic function
We will be using a double heuristic function, i.e., a number of misplaced tiles and the distance between the misplaced tiles.
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
Successor nodes
To get the successor nodes, the program will look for an empty space and the allowed move and will return an array consisting of the available moves and their heuristic values.
def sucessor(self,node=[]): subNode=[] getZeroLocation=node.index(' 0')+1 subNode.extend(node) boundry=self.boundries(getZeroLocation) 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)
Choosing the next node
To choose the next node, the program will look for the node with the minimum heuristic. The program will also save the selected node and will look for this history every time to make sure no redundant move is initiated.
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
puzzler.py
This class contain the code to run this algorithm. You can also use the solve() function in py8puzzle.py to work without the need for graphics.
import pygame, sys, time from pygame.locals import * from py8puzzel import* puzzle=puzzel() #puzzle.Solve() pygame.init() WINDOWWIDTH = 600 WINDOWHEIGHT = 600 BASICFONT = pygame.font.Font(' freesansbold.ttf',50) windowSurface = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT), 0, 32) pygame.display.set_caption(' 8 Puzzle') BLACK = (0, 0, 0) RED = (255, 0, 0) GREEN = (0, 255, 0) BLUE = (0, 0, 255) WHITE=(255,255,255) Text=(0,0,0) blockTOP=0; blockLEFT=0; blocks=[] blockNumber=1 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()
Eight Puzzle Python Find Solution Self Init_state
Source: https://www.codeproject.com/Articles/365553/8-Puzzle-solving-using-the-A-algorithm-using-Pytho