Nov-03-2018, 07:10 AM
Nov-03-2018, 10:40 AM
Show us what you have done (in Python code tags) and explain what doesn't work the way you want. Post also full error traceback message, in case you get errors (in error tags).
You might also want to explain the assignment in more detail, for those of us (like me), who don't know how that game should work.
You might also want to explain the assignment in more detail, for those of us (like me), who don't know how that game should work.
Nov-04-2018, 10:28 AM
(Nov-03-2018, 10:40 AM)j.crater Wrote: [ -> ]Show us what you have done (in Python code tags) and explain what doesn't work the way you want. Post also full error traceback message, in case you get errors (in error tags).
You might also want to explain the assignment in more detail, for those of us (like me), who don't know how that game should work.
from copy import deepcopy class puzzle: def __init__ (self, starting, parent): #Constructor self.board = starting self.parent = parent self.f = 0 self.g = 0 self.h = 0 def manhattan(self): h = 0 for i in range(3): #Manhattan definition for j in range(3): x, y = divmod(self.board[i][j], 3) #getting the remainder and quotient of the current value h += abs(x-i) + abs(y-j) #calculating manhanttan distance return h def goal(self): inc = 0 #checking whether goal state is achieved for i in range(3): for j in range(3): if self.board[i][j] != inc: return False inc += 1 return True def __eq__(self, other): return self.board == other.board #check is boards are equal or not def move_function(curr): curr = curr.board for i in range(3): for j in range(3): #move function to move the tile if curr[i][j] == 0: x, y = i, j break q = [] if x-1 >= 0: b = deepcopy(curr) b[x][y]=b[x-1][y] b[x-1][y]=0 succ = puzzle(b, curr) q.append(succ) if x+1 < 3: b = deepcopy(curr) b[x][y]=b[x+1][y] b[x+1][y]=0 succ = puzzle(b, curr) q.append(succ) if y-1 >= 0: b = deepcopy(curr) b[x][y]=b[x][y-1] b[x][y-1]=0 succ = puzzle(b, curr) q.append(succ) if y+1 < 3: b = deepcopy(curr) b[x][y]=b[x][y+1] b[x][y+1]=0 succ = puzzle(b, curr) q.append(succ) return q def best_fvalue(openList): f = openList[0].f index = 0 for i, item in enumerate(openList): if i == 0: continue if(item.f < f): f = item.f index = i return openList[index], index def AStar(start): openList = [] closedList = [] openList.append(start) while openList: current, index = best_fvalue(openList) if current.goal(): return current openList.pop(index) closedList.append(current) X = move_function(current) for move in X: ok = False #checking in closedList for i, item in enumerate(closedList): if item == move: ok = True break if not ok: #not in closed list newG = current.g + 1 present = False #openList includes move for j, item in enumerate(openList): if item == move: present = True if newG < openList[j].g: openList[j].g = newG openList[j].f = openList[j].g + openList[j].h openList[j].parent = current if not present: move.g = newG move.h = move.manhattan() move.f = move.g + move.h move.parent = current openList.append(move) return None #start = puzzle([[2,3,6],[0,1,8],[4,5,7]], None) start = puzzle([[5,2,8],[4,1,7],[0,3,6]], None) # start = puzzle([[0,1,2],[3,4,5],[6,7,8]], None) #start = puzzle([[1,2,0],[3,4,5],[6,7,8]], None) result = AStar(start) noofMoves = 0 if(not result): print ("No solution") else: print(result.board) t=result.parent while t: noofMoves += 1 print(t.board) t=t.parent print ("Length: " + str(noofMoves))
Nov-04-2018, 03:18 PM
I have actually find this code somewhere... it only use Manhattan as a heuristic function but i also want to use linear conflict and x-y heuristic so that the puzzle can be solved more efficiently. But i am not able to do so !
May-30-2020, 05:54 PM
(Nov-04-2018, 10:28 AM)aliyark145 Wrote: [ -> ][python]
from copy import deepcopy
...
This code is already very efficient (compared to my 3 other 8-puzzle solvers)! The only thing is that the empty cell is at start instead of at the end of the 3x3 matrix, as most n-puzzlers are. I am not sure if it is built to work in this way only., Anyway, I tried to fix this but the way is not evident and it seems it will take some time … If it's worthwhile, can you give me a hint of how to do that.