three_puzzle_bfs_solver.py.py

three_puzzle_bfs_solver.py.py

'''
Using Breadth-First Search to solve the three puzzle
Author: Yuhang Wang
'''

from collections import deque

def isAdjacent(row1, col1, row2, col2):
  if abs(row1-row2) + abs(col1-col2) == 1:
    return True 
  else:
    return False 


# convert index of piece to row number and column number
def index2loc(index):
  row = index / 2
  column = index % 2
  return (row, column)


def goal_test(state):
  if state == ('1', '2', '3', ''):
    return True
  return False


def is_legal(action, state):
  index = state.index(action)
  (row, col) = index2loc(index)
  empty_index = state.index('')
  (empty_row, empty_col) = index2loc(empty_index)
  return isAdjacent(row, col, empty_row, empty_col)


# apply action to state and return the resulting state
def apply_action(action, state):
  index = state.index(action)
  (row, col) = index2loc(index)
  empty_index = state.index('')
  (empty_row, empty_col) = index2loc(empty_index)
  new_state = list(state)
  new_state[index] = ''
  new_state[empty_index] = action
  return tuple(new_state)
  

# initial_state is the tuple (initial positions of pieces)
# we cannot use a list to store state because Python does not allow us to add lists to the explored set
def bfs_three_puzzle(initial_state):
  frontier = deque([(initial_state, [])])  #  node is (state, solution path)
  explored = set([])
  
  actions = ['1', '2', '3'] # each action is to try to move a piece
  
  while (frontier):
    current_node = frontier.popleft()
    print current_node
    current_state = current_node[0]
    solution_path = current_node[1]
    if goal_test(current_state):
      print 'solution found:'
      print solution_path
      return
    explored.add(current_state)
    for action in actions:
      if is_legal(action, current_state):
        child_state = apply_action(action, current_state)
        if child_state not in explored: 
          frontier.append((child_state, solution_path + [action])) # solution path is a list of actions taken to go from initial state to this child state
  
  print 'solution not found'
  return

# a few test cases
bfs_three_puzzle(('1', '2', '', '3'))
bfs_three_puzzle(('1', '3', '', '2'))
bfs_three_puzzle(('3', '', '2', '1'))