8 puzzle solver

8_puzzle_solver.py

import copy
import heapq


class Node(object):

    def __init__(self, cost, moves, board, parent, blank_tile):
        self.cost = cost
        self.moves = moves
        self.board = board
        self.parent = parent
        self.blank_tile = blank_tile

    def __lt__(self, other):
        return (self.cost + self. moves) - (other.cost + other.moves)


class Solution(object):

    def __init__(self, starting_board, target_board):
        self.board = copy.copy(starting_board)
        self.heap = []
        self.target_board = target_board

    def construct_path(self, node):

        path = [node]

        while node.parent:
            path.append(node.parent)
            node = node.parent

        path = list(reversed(path))

        for node in path:
            self.print_board(node.board)
            print("----------------")

    def print_board(self, game_board):
        for row in game_board:
            print(row)

    def is_valid(self, node, d):
        new_pos_x = node.blank_tile[0] + d[0]
        new_pos_y = node.blank_tile[1] + d[1]

        x = len(node.board)
        y = len(node.board[0])

        if (new_pos_x < 0 or new_pos_x >= x) or (new_pos_y < 0 or new_pos_y >= y):
            return False

        return True

    def calculate_cost(self, game_board, target_board):
        cost = 0

        for i, _ in enumerate(game_board):
            for j, _ in enumerate(game_board[i]):

                if game_board[i][j] != "_" and game_board[i][j] != target_board[i][j]:
                    cost += 1

        return cost

    def helper(self, node):

        heapq.heappush(self.heap, node)
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        while self.heap:

            min_cost_node = heapq.heappop(self.heap)

            if self.calculate_cost(min_cost_node.board, self.target_board) == 0:
                return self.construct_path(min_cost_node)

            # generate all the new states
            for d in directions:
                if self.is_valid(min_cost_node, d):
                    new_board = copy.deepcopy(min_cost_node.board)
                    new_blank = (min_cost_node.blank_tile[0] + d[0], min_cost_node.blank_tile[1] + d[1])
                    
                    # swap the blank tile
                    new_board[min_cost_node.blank_tile[0]][min_cost_node.blank_tile[1]],\
                        new_board[new_blank[0]][new_blank[1]] = \
                        new_board[new_blank[0]][new_blank[1]],\
                        new_board[min_cost_node.blank_tile[0]][min_cost_node.blank_tile[1]]
                    
                    # construct the new node
                    new_moves = min_cost_node.moves + 1
                    new_cost = self.calculate_cost(new_board, self.target_board)
                    new_node = Node(new_cost, new_moves, new_board, min_cost_node, new_blank)
                    
                    heapq.heappush(self.heap, new_node)

    def solve(self):
        # create a starting node
        node = Node(0, 0, self.board, None, (1, 2))
        self.helper(node)


if __name__ == "__main__":
    board = [
        ["1", "2", "3"],
        ["5", "6", "_"],
        ["7", "8", "4"]
    ]
    target_board = [
        ["1", "2", "3"],
        ["5", "8", "6"],
        ["_", "7", "4"]
    ]

    Solution(board, target_board).solve()