Optimizing the code for 8-puzzle in Python

Initial thoughts:

1. Why optimize your code when there are 362 880 possibilities, the best way to optimize is to reduce the number of possibilities. The complexity here is O(n²!) meaning that it quickly becomes impossible to compute (4x4 is 20 trillions possibilities and 15 septillions for a 5 by 5).

2. I would argue against using strings in this case because they are immutable, meaning that you need to create new instances all the time. (numpy array ?)

3. The last 50 lines or so feel highly repetitive (as well as the move_xxxx()) and could be improved

import sys
import itertools
import copy
from collections import deque, namedtuple

node_id = 0

# Wheel to make sure the program is running
# Yes this function is ugly but hey, that's just a spinning wheel
def spin(wheel=itertools.cycle(['–', '/', '|', '\\']), rate=1000, spin_count=[0]):
    if not spin_count[0]%rate:
        sys.stdout.write(next(wheel))     # write the next character
        sys.stdout.flush()                # flush stdout buffer (actual character display)
        sys.stdout.write('\b')            # erase the last written char
    spin_count[0] += 1


class SlidingPuzzle:

    directions = {
        'up': (-1, 0),
        'down': (1, 0),
        'left': (0, -1),
        'right': (0, 1)
    }

    def __init__(self, start_board):
        self.start_configuration = str(start_board) + '0'
        self.goal_configuration = '123456780'

    def get_node_id(self, configuration):  # configuration: 123405786999 implies Node 999
        string_configuration = str(configuration)
        string_node_id = string_configuration[9:]
        return string_node_id

    def get_node_orientation(self, configuration):
        string_configuration = str(configuration)
        string_orientation = string_configuration[:9]
        return string_orientation

    def display_board(self, configuration, arg='new'):
        if arg == 'new':
            old_configuration = self._get_old_configuration(configuration)
        elif arg == 'old':
            old_configuration = configuration
        # displays the board's configuration.
        print("\n")
        for row in old_configuration:
            print(row)
        print("\n")
        return

    def _get_old_configuration(self, new_configuration):
        # @new_configuration: 123045678101; 101 is a number
        # returns old_configuration : [['1', '2', '3'], ['0', '4', '5'], ['6', '7', '8']]
        string_new_configuration = str(new_configuration)
        old_configuration = []
        for x in range(0, 3):
            row_list = []
            for element in string_new_configuration[3*x: 3*(x+1)]:
                row_list.append(element)
            old_configuration.append(row_list)
        return old_configuration

    def _get_new_configuration(self, old_configuration):
        # @old_configuration : [['1', '2', '3'], ['0', '4', '5'], ['6', '7', '8']]
        # returns new_configuration: 123045678node_id; node_id is a number
        global node_id  # Made it Global because everytime its called means we are creating a new_node
        node_id += 1
        new_configuration = ''
        for row in old_configuration:
            for each_element in row:
                new_configuration += each_element
        string_node_id = node_id
        string_node_id = str(string_node_id)

        new_configuration += string_node_id
        return new_configuration

    def slider(self, configuration):
        configuration = str(configuration)
        config = self._get_old_configuration(configuration[:9])
        position = [(row, column.index("0"))
                    for row, column in enumerate(config) if '0' in column]
        return position

    def move(self, configuration, direction):
        # The configuration passed to it is the new configuration
        # Moves the slider up if it is possible, otherwise returns false.
        # We need to have updated slider position everytime.
        slider_position = self.slider(configuration)
        dummy_board = self._get_old_configuration(configuration)
        i, j = slider_position[0]
        di, dj = SlidingPuzzle.directions[direction]
        try:
            element = dummy_board[i+di][j+dj]
        except IndexError:
            raise ValueError(f"Impossible to move '{direction}'")
        dummy_board[i+di][j+dj] = '0'
        dummy_board[i][j] = element
        dummy_board = self._get_new_configuration(dummy_board)
        return dummy_board

    def valid_moves(self, configuration):
        # @board_orientation format: [['1', '2', '3'], ['0', '4', '5'], ['6', '7', '8']]
        # returns valid moves in a list form: ['up', 'down', 'right', 'left']

        valid_moves_list = ['up', 'down', 'right', 'left']
        board_orientation = self._get_old_configuration(configuration)
        [(i, j)] = [(row, column.index('0'))
                    for row, column in enumerate(board_orientation) if '0' in column]
        if i+1 == 3:
            valid_moves_list.remove('down')
        if i-1 == -1:
            valid_moves_list.remove('up')
        if j+1 == 3:
            valid_moves_list.remove('right')
        if j-1 == -1:
            valid_moves_list.remove('left')

        return valid_moves_list

    def does_solution_exist(self, configuration):
        string_config = str(configuration)
        temp_list = []
        for number in string_config[:9]:
            if number != '0':
                temp_list.append(int(number))

        inversions = 0
        for i in range(0, 8):
            for j in range(i, 8):
                if temp_list[i] > temp_list[j]:
                    inversions += 1
        return bool(inversions % 2 == 0)

    # Brute Force Algorithm

    def breadth_first_search(self):

        start = self.start_configuration
        print('Original Board: ')
        self.display_board(start)

        nodes_to_be_visited = deque()
        nodes_to_be_visited.append(self.get_node_id(start))
        visited_nodes = []
        node_dictionary = {'0': self.get_node_orientation(start)}

        # Does solution Exists?
        if self.does_solution_exist(start) < 1:
            print("No Solution exists")
            return False

        else:
            print('Solution Exists for this Puzzle Configuration\n')

            found = False
            while (nodes_to_be_visited) and not found:  # While queue is not empty
                current_node = nodes_to_be_visited.pop()  # Pop the queue to get node id
                # Fetch its configuration from the dictionary
                current_configuration = node_dictionary.get(current_node)

                # if current visit is our goal configuration:
                if current_configuration == self.goal_configuration:
                    print("\nWe found the solution: \n")
                    self.display_board(current_configuration)
                    break

                # If current visit is not the goal configuration
                if current_configuration != self.goal_configuration:

                    # And if it is the first time we are visiting the ndoe... Let's register its children
                    if current_node not in visited_nodes:
                        visited_nodes.append(current_node)
                        possible_moves = self.valid_moves(
                            current_configuration)

                        for move in possible_moves:
                            configuration = self.move(
                                current_configuration, move)
                            node_id_local = self.get_node_id(configuration)
                            node_configuration_local = self.get_node_orientation(
                                configuration)
                            node_dictionary[node_id_local] = node_configuration_local
                            nodes_to_be_visited.append(node_id_local)
                            if node_configuration_local == self.goal_configuration:
                                print("\nWe found the solution: \n")
                                self.display_board(
                                    node_configuration_local)
                                found = True
                                break
                spin() # Just to make sure it is still running
# Helper Code


access = SlidingPuzzle('123405786')
access.breadth_first_search()

Here is what I have changed (> means added, < means deleted):

0a1,2
> import sys
> import itertools
5a8,16
> # Wheel to make sure the program is running
> # Yes this function is ugly but hey, that's just a spinning wheel
> def spin(wheel=itertools.cycle(['–', '/', '|', '\\']), rate=1000, spin_count=[0]):
>     if not spin_count[0]%rate:
>         sys.stdout.write(next(wheel))     # write the next character
>         sys.stdout.flush()                # flush stdout buffer (actual character display)
>         sys.stdout.write('\b')            # erase the last written char
>     spin_count[0] += 1
> 
8a20,26
>     directions = {
>         'up': (-1, 0),
>         'down': (1, 0),
>         'left': (0, -1),
>         'right': (0, 1)
>     }
> 
69c87,88
<     def move_up(self, configuration):  # The configuration passed to it is the new configuration
---
>     def move(self, configuration, direction):
>         # The configuration passed to it is the new configuration
74,131c93,100
<         if slider_position[0][0] == 0:  # when slider is in first row
<             print("\nError: Slider can't move above from current position \n")
<             return False
<         else:
<             (i, j) = slider_position[0]
<             element = dummy_board[i-1][j]
<             dummy_board[i-1][j] = '0'
<             dummy_board[i][j] = element
<         dummy_board = self._get_new_configuration(dummy_board)
<         return dummy_board
< 
<     def move_down(self, configuration):
<         # Moves the slider down if it is possible, otherwise returns false.
<         # We need to have updated slider position everytime.
<         slider_position = self.slider(configuration)
<         dummy_board = self._get_old_configuration(configuration)
<         if slider_position[0][0] == 2:  # when slider is in third row
<             print("\nError: Slider can't move down from current position \n")
<             return False
<         else:
<             (i, j) = slider_position[0]
<             element = dummy_board[i+1][j]
<             dummy_board[i+1][j] = '0'
<             dummy_board[i][j] = element
<         dummy_board = self._get_new_configuration(dummy_board)
<         return dummy_board
< 
<     def move_right(self, configuration):
<         # Moves the slider right if it is possible, otherwise returns false.
<         # We need to have updated slider position everytime.
<         slider_position = self.slider(configuration)
<         dummy_board = self._get_old_configuration(configuration)
<         if slider_position[0][1] == 2:  # When slider is in third column
<             print(slider_position)
<             print("\nError: Slider can't move right from current position \n")
<             print('current_configuration being sent to move_right(): ', configuration)
<             return False
<         else:
<             (i, j) = slider_position[0]
<             element = dummy_board[i][j+1]
<             dummy_board[i][j+1] = '0'
<             dummy_board[i][j] = element
<         dummy_board = self._get_new_configuration(dummy_board)
<         return dummy_board
< 
<     def move_left(self, configuration):
<         # Moves the slider up if it is possible, otherwise returns false.
<         # We need to have updated slider position everytime.
<         slider_position = self.slider(configuration)
<         dummy_board = self._get_old_configuration(configuration)
<         if slider_position[0][1] == 0:  # When slider is in first column
<             print("\nError: Slider can't move left from current position \n")
<             return False
<         else:
<             (i, j) = slider_position[0]
<             element = dummy_board[i-1][j]
<             dummy_board[i][j-1] = '0'
<             dummy_board[i][j] = element
---
>         i, j = slider_position[0]
>         di, dj = SlidingPuzzle.directions[direction]
>         try:
>             element = dummy_board[i+di][j+dj]
>         except IndexError:
>             raise ValueError(f"Impossible to move '{direction}'")
>         dummy_board[i+di][j+dj] = '0'
>         dummy_board[i][j] = element
180d148
<         parent_children_dictionary = []  # Will update this next time
191c159
<             while (nodes_to_be_visited) and (found == False) > 0:  # While queue is not empty
---
>             while (nodes_to_be_visited) and not found:  # While queue is not empty
212,271c180,193
<                             # If moving left is allowed
<                             if move == 'left':
<                                 configuration = self.move_left(
<                                     current_configuration)
<                                 node_id_local = self.get_node_id(configuration)
<                                 node_configuration_local = self.get_node_orientation(
<                                     configuration)
<                                 node_dictionary[node_id_local] = node_configuration_local
<                                 nodes_to_be_visited.append(node_id_local)
<                                 if node_configuration_local == self.goal_configuration:
<                                     print("\nWe found the solution: \n")
<                                     self.display_board(
<                                         node_configuration_local)
<                                     found = True
<                                     break
< 
<                             elif move == 'right':
<                                 configuration = self.move_right(
<                                     current_configuration)
<                                 node_id_local = self.get_node_id(configuration)
<                                 node_configuration_local = self.get_node_orientation(
<                                     configuration)
<                                 node_dictionary[node_id_local] = node_configuration_local
<                                 nodes_to_be_visited.append(node_id_local)
<                                 if node_configuration_local == self.goal_configuration:
<                                     print("\nWe found the solution: \n")
<                                     self.display_board(
<                                         node_configuration_local)
<                                     found = True
<                                     break
< 
<                             elif move == 'up':
<                                 configuration = self.move_up(
<                                     current_configuration)
<                                 node_id_local = self.get_node_id(configuration)
<                                 node_configuration_local = self.get_node_orientation(
<                                     configuration)
<                                 node_dictionary[node_id_local] = node_configuration_local
<                                 nodes_to_be_visited.append(node_id_local)
<                                 if node_configuration_local == self.goal_configuration:
<                                     print("\nWe found the solution: \n")
<                                     self.display_board(
<                                         node_configuration_local)
<                                     found = True
<                                     break
< 
<                             elif move == 'down':
<                                 configuration = self.move_down(
<                                     current_configuration)
<                                 node_id_local = self.get_node_id(configuration)
<                                 node_configuration_local = self.get_node_orientation(
<                                     configuration)
<                                 node_dictionary[node_id_local] = node_configuration_local
<                                 nodes_to_be_visited.append(node_id_local)
<                                 if node_configuration_local == self.goal_configuration:
<                                     print("\nWe found the solution: \n")
<                                     self.display_board(
<                                         node_configuration_local)
<                                     found = True
<                                     break
---
>                             configuration = self.move(
>                                 current_configuration, move)
>                             node_id_local = self.get_node_id(configuration)
>                             node_configuration_local = self.get_node_orientation(
>                                 configuration)
>                             node_dictionary[node_id_local] = node_configuration_local
>                             nodes_to_be_visited.append(node_id_local)
>                             if node_configuration_local == self.goal_configuration:
>                                 print("\nWe found the solution: \n")
>                                 self.display_board(
>                                     node_configuration_local)
>                                 found = True
>                                 break
>                 spin() # Just to make sure it is still running

I will read your code more in depth and update this answer.