5
\$\begingroup\$

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]

A typical 8-puzzle with Initial configuration and goal configuration

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

  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)}
    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')
access.breadth_first_search()
\$\endgroup\$
5
  • \$\begingroup\$ This looks interesting, Can you add some information regarding what is 8-puzzle? \$\endgroup\$ Feb 25 '19 at 15:40
  • \$\begingroup\$ @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] \$\endgroup\$ Feb 25 '19 at 16:04
  • \$\begingroup\$ 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. \$\endgroup\$
    – Benoît P
    Feb 25 '19 at 16:25
  • \$\begingroup\$ @SarveshThakur could you please add comment The 15-puzzle .... to question description as well. \$\endgroup\$ Feb 26 '19 at 11:41
  • \$\begingroup\$ 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().) \$\endgroup\$
    – Apostolos
    Jun 2 '20 at 5:44
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Here are a couple of points:

  1. You need to move your documentation and your comments into docstrings:

    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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.