Please help me fix the bug in 8 Puzzle Solver using simpleai.search.astar

123 views

Skip to first unread message

Ravindra Thadani

unread,

Mar 31, 2021, 4:27:33 AM3/31/21

to simpleai

from simpleai.search import astar, SearchProblem

class PuzzleSolver(SearchProblem):
    def __init__(self, initial):
        self.goal = '1-2-3\n4-5-6\n7-8-_'

        #lets create a cache for goal positions of all the values
        matrix = self.string_to_list(self.goal)
        self.goal_position = {}
        for x in '12345678_':
            self.goal_position[x] = self.get_coordinates(matrix, x)

        SearchProblem.__init__(self, initial_state= initial)

    #A method that gets current state of the puzzle solver
    #and returns a list of the numbers that can be moved into the empty space
    def actions(self, curr_state):
        matrix = self.string_to_list(curr_state)
        row_empty, col_empty = self.get_coordinates(matrix, '_')
        moves = []
        if row_empty > 0:
            moves.append(matrix[row_empty-1][col_empty])
        if row_empty < 2:
            moves.append(matrix[row_empty+1][col_empty])
        if col_empty > 0:
            moves.append(matrix[row_empty][col_empty-1])
        if col_empty < 2:
            moves.append(matrix[row_empty][col_empty+1])
        return moves

    #A method that accepts current state and action. It returns the new state
    #that results by application of the action.
    def result(self, curr_state, action):
        matrix = self.string_to_list(curr_state)
        row_empty, col_empty = self.get_coordinates(matrix, '_')
        row_action, col_action = self.get_coordinates(matrix, action)
        #swap
        matrix[row_empty][col_empty], matrix[row_action][col_action] = matrix[row_action][col_action], matrix[row_empty][col_empty]

        new_state = self.list_to_string(matrix)
        return new_state

    #Termination criteria for A*
    def is_goal(self, curr_state):
        return curr_state == self.goal

    #Heuristic Search: A method that returns an estimate of distance from the current state to the goal
    #using the Manhattan Distance
    def heuristic(self, curr_state):
        matrix = self.string_to_list(curr_state)
        distance = 0
        for number in '12345678_':
            row_number, col_number = self.get_coordinates(matrix, number)
            goal_row_number, goal_col_number = self.goal_position[number]

            distance += abs(row_number - goal_row_number) + abs(col_number - goal_col_number)
        return distance

    #helper methods
    def string_to_list(self, input_string):
        data = [item.split('-') for item in input_string.split('\n')]
        return data

    def list_to_string(self, matrix):
        w = '\n'.join(['-'.join(x) for x in matrix])
        return w

    def get_coordinates(self, matrix, element):
        for i, row in enumerate(matrix):
            for j, col in enumerate(row):
                if col == element:
                    return i,j

        return None

    def solve(self):
        #invoking A*
        result = astar(self)
        path = result.path()
        action, state = path.pop(0)
        print('Initial State')
        print(state)

        for action, state in path:
            print('After moving ', action, 'into empty space')
            print(state)

        print('Goal Achieved')

def main():
    #test cases
    initial = '1-_-2\n6-3-4\n7-5-8' #working
    #initial = '1-2-3\n6-_-4\n7-5-8' #not working
    initial = '1-2-_\n6-3-4\n7-5-8' # working
    initial = '_-1-2\n6-3-4\n7-5-8' # working
    #initial = '1-6-2\n_-3-4\n7-5-8' #not working
    initial = '1-4-5\n6-3-8\n7-2-_' # working
    #initial = '1-4-2\n6-3-_\n7-5-8' # not working
    initial = '1-4-5\n6-8-3\n_-2-7' # working
    #initial = '1-4-_\n6-8-3\n5-2-7' # not working
    #initial = '1-4-5\n6-8-3\n2-7-_' # working
    #initial = '1-4-6\n5-8-3\n2-7-_' # not working
    #initial = '7-3-4\n2-_-8\n5-1-6' #not working

    ps = PuzzleSolver(initial)
    ps.solve()

main()

fisa

unread,

Apr 12, 2021, 1:07:20 PM4/12/21

to simpleai

This has been answered in this Github issue:

https://github.com/simpleai-team/simpleai/issues/76#issuecomment-817973732

But for future occasions: you need to be more specific. You can't just send a random piece of code to a strange person with just a title "fix it". You need to explain what are you trying to do, what are you expecting as a result, what results are you getting instead, why do you think that's a problem in the lib and not your code, etc.

Remember: the other person can't read your mind. You have to explain the context of your issue :)

Bye! And good luck,

--
Has recibido este mensaje porque estás suscrito al grupo "simpleai" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a simpleai+u...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/simpleai/093dc496-f704-4732-83cc-b18f6dc81e34n%40googlegroups.com.