Question

Write a program in a language of your choice to perform a search using the A* algorithm for the eight puzzle problem, in which numbers may be shifted one space at a time to transform the initial state into the goal state (see p. 103 – 3rd Ed., pp. 105-106 – 2nd Ed. of the text).

2. a)

Use the start state-goal state combination given in pp. 103, Figure 3.28 (3rd Ed.), [pp. 105,

Figure 4.7 (2rd Ed.)], as (start_1, goal_1) (see page 2).

2. b) Use a new start state, which is given in page 2, the same goal state (start_2, goal_1).

3. c) Use a different goal state (the blank is now at the bottom right corner - see page 2),

   and the same start state as part a (start_1, goal_2).

4. d) Use a the same start state as part b, and the same goal state as part c

   (start_2, goal_2) (see page 2).

5. e) Also use { (start_3, goal_1), (start_3, goal_2), (start_3, goal_3), (start_1, goal_3),

   (start_2, goal_3) } pairs given in page 2.

3. Use two different set of heuristic functions to estimate distance from the goal
   (See pp. 103 – 3rd Ed, p. 106 – 2nd Ed.)
   h1: the number of misplaced tiles
   h2: the sum of the distances of tiles from their goal positions (Manhattan distance)

4. Write a report comparing the performance of the two heuristics on the nine different sets of (start_x, goal_x) combinations of part 2.

   Performance measure: the length of the solution path (from the start state to the goal), and the actual time it takes to find the solution (i.e., to reach the goal state).

Answer 1

from copy import deepcopy

class puzzle:
    def __init__ (self, starting, parent):
        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):
            for j in range(3):
                x, y = divmod(self.board[i][j], 3)
                h += abs(x-i) + abs(y-j)
        return h


    def goal(self):
        inc = 0
        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

def move_function(curr):
    curr = curr.board
    for i in range(3):
        for j in range(3):
            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))