8 Puzzle.
Write a program that solves the problem using the algorithm A*.
Problem. 
http://en.wikipedia.org/wiki/Fifteen_puzzle 
I think everyone knows the game of nickels and dimes. This is a slightly simplified version - a game of 8.
Our goal is to rearrange the blocks so that they are arranged in ascending order, and to make as few steps as possible. You are allowed to move blocks horizontally and vertically into an empty square.
 
Best-first search.
We describe a solution to the problem that illustrates one of the artificial intelligence algorithms known as the A* search algorithm. We define the board as a search node (i.e., the result of a move is a board with elements arranged in a certain order), and we need to memorize the number of steps to be taken to reach this search node and the previous search node.
First, we insert the initial search node (input location, 0 steps, null previous search node) into the priority queue. After that, we remove the search node with the lowest priority from the queue and insert all its successors (those that can be reached in one step from this node) into the queue. We repeat this procedure until we get a node from the queue that corresponds to the final state (a board with all the blocks in their places).
The success of our activity depends on the choice of the priority function. Let's consider two functions:
The Hamming function - the number of blocks in the wrong positions, plus the number of steps taken to reach the current search node. It is intuitively clear that a position on the board with a small number of blocks out of place is close enough to the desired state.
The Manhattan function is the sum of the Manhattan distances (the sum of the vertical and horizontal distance) from the current position of each block to the desired state, plus the number of steps taken to reach the current state.
Example:
 
Optimization.
As you can see, Best-first search will have one small problem. We will add the previous state to PQ.
 
Therefore, we should not add to the PQ a state that is previous to the current state.
Problem.
Not all initial states have a solution.
 
Solvability condition. We change the blocks in pairs until the blocks are arranged in the correct order. If there are an even number of such permutations, then the problem is solvable, otherwise it is unsolvable.
API.
The initial classes are lower in the text. You must use MinPQ.

board.py:

class Board:
    def __init__(self, dimension, blocks) -> None:
        self._dimension = dimension
        self._blocks = blocks

    def dimension(self) -> int:
        return self._dimension

    def hamming(self) -> int:
        # hamming distance
        pass

    def manhattan(self) -> int:
        # manhattan distance
        pass

    def is_goal(self) -> bool:
        # check if this board is solution
        pass

    def __eq__(self, other) -> bool:
        # check that this board is equal to other
        pass

    def neighbors(self) -> list:
        # should return list of neighbor boards
        pass

    def __str__(self) -> str:
        # string representation
        pass


solver.py:

from board import Board


class Solver:
    def __init__(self, board):
        self._initial_board = board

    def is_solvable(self) -> bool:
        # check if board is solvable
        pass

    def moves(self) -> int:
        # return minimal count of steps to solution or -1 if it does not have it
        pass

    def solution(self) -> list:
        # list of sequence of boards in the shortest path or null if we do not have solution
        pass


def read_board_data() -> tuple[int, list[list[int]]]:
    # read dimension and initial list[][] from file
    pass


def main():
    board = Board(*read_board_data())
    solver = Solver(board)

    if not solver.is_solvable():
        print("Board does not have solutions")
    else:
        print(f"Minimal number of steps {solver.moves()}")
        for board in solver.solution():
            print(board)


if __name__ == "__main__":
    main()