Question
My assignment is to implement the 8-puzzle using the a* algorithm. below is the assignment itself: My code I have currently works for simple initial
My assignment is to implement the 8-puzzle using the a* algorithm. below is the assignment itself:
My code I have currently works for simple initial states; however using more complex states causes my program to enter an endless loop. I have spent hours trying to debug my program, but I cannot seem to find where the problem would be.
In my start() method, I have two init_pos variables. The second one solves without problems, but switching the 2 and 3(the orientation of the first init_pos) causes the endless loop to begin.
Any help is greatly appreciated.
MY CODE:
from copy import deepcopy goal = [[1, 2, 3], [8, 0, 4], [7, 6, 5]] class Puzzle: def __init__(self, start_pos, parent): self.space = start_pos self.parent = parent self.h = 0 self.g = 0 self.f = 0 # Counts how many elements in the play space are not in the correct position def h_val(self): count = 0 h = 0 for i in range(3): for j in range(3): if self.space[i][j] == 0: count += 1 continue elif self.space[i][j] != goal[i][j]: h += 1 count += 1 return h # checks is the current play space is in the goal position def is_goal_state(self): for i in range(3): for j in range(3): if self.space[i][j] != goal[i][j]: return False # increment += 1 return True def __eq__(self, other): return self.space == other.space # gets possible moves def move(current): current = current.space for i in range(3): for j in range(3): if current[i][j] == 0: x, y = i, j break move_list = [] if x - 1 >= 0: copy = deepcopy(current) copy[x][y] = copy[x - 1][y] copy[x - 1][y] = 0 temp = Puzzle(copy, current) move_list.append(temp) if x + 1 = 0: copy = deepcopy(current) copy[x][y] = copy[x][y - 1] copy[x][y - 1] = 0 temp = Puzzle(copy, current) move_list.append(temp) if y + 1 2) 8 Puzzle Problem: The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Start with a random state. The goal state is listed below
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started