8 puzzle solver using DFS

8_puzzle.py

#!/usr/bin/env python3

def swap(l, i, j):
    m = l[::]
    m[i], m[j] = l[j], l[i]
    return m

class Puzzle:
    def __init__(self, initial_state=[0, 1, 3, 2, 4, 8, 5, 6, 7], goal_state=[1, 2, 3, 4, 5, 6, 7, 8, 0]):
        if len(initial_state) != len(goal_state):
            raise ValueError("Initial and goal states don't match in dimension")
        self.initial_state = initial_state
        self.goal_state = goal_state
        self.n = len(goal_state) ** 0.5

    def is_goal(self, state):
        """
            Check if the state is a goal state
        """
        return state == self.goal_state

    def find_empty(self, state):
        """
            Find the position of empty space (0)
        """
        return state.index(0)

    def get_moves(self, state):
        """
            Finds the all the next possible moves that can be reaced from current position

            Returns the list of 2d (row,col) position
        """
        pos = self.find_empty(state)
        pos_2d = self.get_row_col(pos)
        next_states = []
        row, col = pos_2d
        # north
        if row > 0:
            next_states.append( (row-1, col) )
        # east
        if col < self.n - 1:
            next_states.append( (row, col+1) )
        # south
        if row < self.n - 1:
            next_states.append( (row + 1, col) )
        # west
        if col > 0:
            next_states.append( (row, col-1 ) )
        return next_states

    def get_next_states(self, state):
        """
            Returns the list of possible next states
        """
        pos = self.find_empty(state)
        pos_2d = self.get_row_col(pos)
        next_states = []
        row, col = pos_2d
        # north
        if row > 0:
            next_pos = self.get_1d_pos(row-1, col)
            next_states.append( swap (state, pos, next_pos) )
        # east
        if col < self.n - 1:
            next_pos = self.get_1d_pos(row, col + 1)
            next_states.append( swap (state, pos, next_pos) )
        # south
        if row < self.n - 1:
            next_pos = self.get_1d_pos(row + 1, col)
            next_states.append( swap (state, pos, next_pos) )
        # west
        if col > 0:
            next_pos = self.get_1d_pos(row, col-1)
            next_states.append( swap (state, pos, next_pos) )
        return next_states

    def get_row_col(self, flat_index):
        """
            Get 2d position of the 1d index
        """
        if flat_index < 0 or flat_index >= (self.n ** 2) :
            raise ValueError("Invalid 1d index")
        return ( (int)(flat_index / self.n), (int)(flat_index % self.n))

    def get_1d_pos(self, row, col):
        """
            Finds the 1d index from given 2d position
        """
        return (int)(col + self.n * row)



def main():
    initial_state = [0, 1, 3, 2, 4, 8, 5, 6, 7]
    goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0]

    puzzle = Puzzle(initial_state, goal_state)

    state = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    print(puzzle.is_goal(state))
    print(puzzle.find_empty(state))
    print(puzzle.get_moves(state))
    print(puzzle.get_next_states(state))

    l = [1,2,3,4,5]
    m = swap(l, 0, 1)

if __name__ == "__main__":
    main()