Question

Write a Python program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.

The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).

     1 3            1      3        1 2 3         1 2 3        1 2 3

4 2 5   =>   4 2 5   => 4     5   => 4    5     => 4 5 6

7 8 6          7 8 6          7 8 6        7 8 6         7 8

initial           1 left              2 up               5 left            goal

Best-first search. Now, we describe a solution to the problem that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions:

• Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.

Manhattan priority function. The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the search node

Input and output formats. The input and output format for a board is the board size N followed by the N-by-N initial board, using 0 to represent the blank square.

more puzzle04.txt

3

0 1 3

4 2 5

7 8 6

Solver puzzle04.txt

Minimum number of moves = 4

3

0 1 3

4 2 5

7 8 6

3

1 0 3

4 2 5

7 8 6

3

1 2 3

4 0 5

7 8 6

3

1 2 3

4 5 0  

7 8 6

3

1 2 3

4 5 6

7 8 0

more puzzle-unsolvable3x3.txt

3

1 2 3

4 5 6

8 7 0

Solver puzzle3x3-unsolvable.txt

Unsolvable puzzle

Your program should work correctly for arbitrary N-by-N boards (for any 1 ≤ N < 128), even if it is too slow to solve some of them in a reasonable amount of time.

Answer 1

It contains two files py8puzzle.py and puzzler.py find below and do upvote thank you.

py8puzzle.py

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=[]

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 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)

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)

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

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()

Please contact me if you have any queries.

Thank you :)