I created a Nine puzzle solver using the Taboo search. But this is not enough smart to solve difficult instances...

nine.py

import logging
from copy import copy
from typing import List


class Nine:
    EMPTY_GRID = 0

    _DISTANCE_MAP = [
        [0, 1, 2, 3, 2, 3, 4, 3, 4, 5],  # 0
        [1, 0, 1, 2, 1, 2, 3, 2, 3, 4],  # 1
        [2, 1, 0, 1, 2, 1, 2, 3, 2, 3],  # 2
        [3, 2, 1, 0, 3, 2, 1, 4, 3, 2],  # 3
        [2, 1, 2, 3, 0, 1, 2, 1, 2, 3],  # 4
        [3, 2, 1, 2, 1, 0, 1, 2, 1, 2],  # 5
        [4, 3, 2, 1, 2, 1, 0, 3, 2, 1],  # 6
        [3, 2, 3, 4, 1, 2, 3, 0, 1, 2],  # 7
        [4, 3, 2, 3, 2, 1, 2, 1, 0, 1],  # 8
        [5, 4, 3, 2, 3, 2, 1, 2, 1, 0],  # 9
    ]

    _MOVE_MAP = [
        [1],  # 0
        [0, 2, 4],  # 1
        [1, 3, 5],  # 2
        [2, 6],  # 3
        [1, 5, 7],  # 4
        [2, 4, 6, 8],  # 5
        [3, 5, 9],  # 6
        [4, 8],  # 7
        [5, 7, 9],  # 8
        [6, 8],  # 9
    ]

    def __init__(self, state: list):
        self.state = state

    def next_nines(self) -> List['Nine']:
        res = []
        empty_position = self.state.index(self.EMPTY_GRID)
        movable = self._MOVE_MAP[empty_position]
        for m in movable:
            next_state = self.swap(copy(self.state), empty_position, m)
            res.append(Nine(next_state))
        return res

    @classmethod
    def swap(cls, state: list, i: int, j: int):
        tmp = state[i]
        state[i] = state[j]
        state[j] = tmp
        return state

    @classmethod
    def distance(cls, nine1: 'Nine', nine2: 'Nine'):
        s = 0
        for i, a in enumerate(nine1.state):
            j = nine2.state.index(a)
            s += cls._DISTANCE_MAP[i][j]
        return s


class NineSolver:
    GOAL = Nine([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    MAX_TABOO = 10

    def __init__(self):
        self.history = []

    def solve(self, initial: Nine):
        i = 0
        taboo_list = []
        current = initial
        current_d = Nine.distance(current, self.GOAL)
        while True:
            i += 1
            if i > 1000:
                break

            self.history.append(current)
            logging.info('Current state (distance): {} ({})'.format(current.state, current_d))

            best_d = None
            next_nine = None
            next_nines = current.next_nines()
            for nine in next_nines:
                if nine.state in taboo_list:
                    continue

                d = Nine.distance(nine, self.GOAL)
                if d == 0:
                    logging.info('Found the solution!')
                    logging.info('Final state (distance): {} ({})'.format(current.state, current_d))
                    return

                if best_d is None or d < best_d:
                    best_d = d
                    next_nine = nine

            if next_nine is not None:
                current = next_nine
                current_d = best_d

            taboo_list.append(current.state)
            if len(taboo_list) > self.MAX_TABOO:
                taboo_list = taboo_list[1:]


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)

    sample1 = Nine([1, 0, 2, 3, 4, 5, 6, 7, 8, 9])
    sample2 = Nine([0, 1, 5, 3, 2, 4, 6, 7, 8, 9])
    sample3 = Nine([1, 4, 6, 2, 7, 5, 3, 8, 9, 0])  # This instance cannot be solved...

    s = NineSolver()
    s.solve(sample2)