# Optimizing the code for 8-puzzle in Python

I am new to programming and I am trying to solve the 8-puzzle using brute force algorithm. The code works for very simple puzzle configuration but freaks out when the even a modest puzzle is input to it. Initially I was working with a format for board as:

[['1','2','3'],['4','5','6'],['7','0','8']]


But after some suggestions, I changed it to '123456708'

Description of 8-Puzzle Problem: The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. Missing tile space is moved to form a regular pattern such 12345678_, where '_' denotes the missing tile[Wikipedia]

import copy
from collections import deque, namedtuple

node_id = 0

class SlidingPuzzle:

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_up(self, configuration):# The configuration passed to it is the new configuration
# Moves the slider up if it is possible, otherwise returns false.
slider_position = self.slider(configuration) # We need to have updated slider position everytime.
dummy_board = self._get_old_configuration(configuration)
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.
slider_position = self.slider(configuration) # We need to have updated slider position everytime.
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.
slider_position = self.slider(configuration) # We need to have updated slider position everytime.
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.
slider_position = self.slider(configuration) # We need to have updated slider position everytime.
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
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

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)}
parent_children_dictionary = []# Will update this next time

# 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 (found == False) > 0:# While queue is not empty
current_node = nodes_to_be_visited.pop()# Pop the queue to get node id
current_configuration = node_dictionary.get(current_node)# Fetch its configuration from the dictionary

# 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:
# 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
# Helper Code

access = SlidingPuzzle('123405786')

• This looks interesting, Can you add some information regarding what is 8-puzzle? Feb 25, 2019 at 15:40
• @422_unprocessable_entity The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. Missing tile space is moved to form a regular pattern such 12345678_, where '_' denotes the missing tile[Wikipedia] Feb 25, 2019 at 16:04
• I will agree with @422_unprocessable_entity that the questions should be self contained as much as possible and adding a little description in the post itself would be a plus. How about adding this image. Feb 25, 2019 at 16:25
• @SarveshThakur could you please add comment The 15-puzzle .... to question description as well. Feb 26, 2019 at 11:41
• This is a very inefficient 8-puzzle solver. (I have timed it using various configurations.) I believe because BFS algo is used, instead of A* search, which is the standard for 8-puzzle solvers. What is good and original although in this code is the check about its solvability at start. (BTW, don't use print('\n'): it adds an extra, redundant empty line. Use just print().) Jun 2, 2020 at 5:44

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

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
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')



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


Here are a couple of points:

class SlidingPuzzle:

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


becomes:

class SlidingPuzzle:
""" The 15-puzzle (also called Gem Puzzle, Boss Puzzle,
Game of Fifteen, Mystic Square and many others) is
a sliding puzzle that consists of a frame of numbered
square tiles in random order with one tile missing.
The puzzle also exists in other sizes, particularly
the smaller 8-puzzle.
"""
def __init__(self, start_board):
""" Construct a new puzzle from a starting configuration.
The starting configuration is a string containing all
the numbers from 1..8, plus 0 or underscore ('_')
where the empty cell should be. The numbers are
considered to be in order from top to bottom, left to
right, so that "1234_5678" represents a puzzle like:

1 2 3
4 _ 5
6 7 8
"""
self.start_configuration = str(start_board) + '0'
self.goal_configuration = '123456780'

2. Validate your parameters during the __init__ call so you won't have to do it again! Check that the right digits, underscore, spaces, etc. are present or deleted or whatever. Make sure nothing is duplicated.

3. You waste a lot of time converting from "string" to "square" format. Just stop doing that and re-write your code in string terms always.

def slider(self, configuration):
...
config = self._get_old_configuration(configuration[:9])
...

def move_up(self, configuration):
slider_position = self.slider(configuration) # We need to have updated slider position everytime.
dummy_board = self._get_old_configuration(configuration)


Notice that your move_up called slider (which called _get_old_configuration) and then move_up called _get_old_configuration itself! You just called the function, threw away the result, and called the function again.

What is worse, slider builds a matrix that never gets used. You only use the current position of the slider to check whether you can move up or not.

Think about your board as a string: "123456789". The first three values are the top row. The last three values are the bottom row. Now think about the left and right columns: you can just compute an index into the string and use index % 3 to determine what column a character is in: index % 3 == 0 means left column. == 2 means right column.

So knowing the index of the slider (which there's str.index for that) lets you know the row or column as well. Rather than call str.index four times, go ahead and build a Sequence[Sequence[Callable]] that contains the methods to be called:

self.slider_index_to_called_methods = (
# 0: top left
(self.move_right, self.move_down),
# 1: top middle
(self.move_left, self.move_right, self.move_down),
...
# 8: bottom right
(self.move_up, self.move_left),
)


Now you can look up the methods to try using a single call to str.index(), iterate over them, and not do any checking or decomposition.

Similarly, you know how to "move" in string-only format. Just swap the slider position (index) with a character either one away (left/right) or three away (up/down).

def move_up(self, configuration, index):
new_index = index - 3
b = configuration.board
new_b = b[:new_index] + b[index] + b[new_index+1:index] \
+ b[new_index] + b[index+1:]
new_configuration = Configuration(new_b)
return new_configuration

4. You waste a lot of time encoding and decoding the node_id from your strings. Just make a separate data object! collections.namedtuple is perfect for this:

Configuration = collections.namedtuple('Configuration', 'board id')


You can subclass the new type to provide your own __init__ method, and use that to implement the global node_id += 1 logic.