Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
8 puzzle game
#1
I need help on this home assignment. I have to implement using linear conflict and x-y heuristic any help regarding this !
Reply
#2
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.
Reply
#3
(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))
Reply
#4
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 !
Reply
#5
(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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  A sign-Reversal Puzzle HY2000 2 2,434 Dec-05-2019, 11:55 AM
Last Post: HY2000
  Cross word puzzle solve using python constraint library aliyark145 1 3,247 Nov-29-2018, 10:53 AM
Last Post: Larz60+
  Simple Eight-Puzzle not working! BenjaminDJ 2 3,131 May-04-2018, 12:17 PM
Last Post: BenjaminDJ
  Magic Square Puzzle Harnick 1 4,843 Aug-09-2017, 04:51 PM
Last Post: nilamo
  Image Puzzle Digitalchemist 6 7,219 Jun-05-2017, 07:56 PM
Last Post: micseydel

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020