hw1.py

import Queue 
# Boolean used to switch on/off debug output
debug = False

# Function for printing the puzzle state to the console
def print_board(board):
    print("- - - - - - - - - - -")
    
    print("{0:4} {1:4} {2:4} {3:4}".format(board[0], board[1], board[2], board[3]))
    print("{0:4} {1:4} {2:4} {3:4}".format(board[4], board[5], board[6], board[7]))
    print("{0:4} {1:4} {2:4} {3:4}".format(board[8], board[9], board[10], board[11]))
    print("{0:4} {1:4} {2:4} {3:4}".format(board[12], board[13], board[14], board[15]))
    
    print("- - - - - - - - - - -")
    print("")

# Function for getting the row of the tile on the board given by the index
def getRow(index):
    if index >= 0 and index <= 3:
        return 0
    elif index >= 4 and index <= 7:
        return 1
    elif index >= 8 and index <= 11:
        return 2
    else:
        return 3

# Function for getting the column of the tile on the board given by the index
def getCol(index):
    if index == 0 or index == 4 or index == 8 or index == 12:
        return 0
    elif index == 1 or index == 5 or index == 9 or index == 13:
        return 1
    elif index == 2 or index == 6 or index == 10 or index == 14:
        return 1
    else:
        return 3

# Function for getting the estimated cost for the heuristic
def getCost(list_0, list_1, algorithm):
    cost = 0
    if algorithm == 2:
        for i in range(len(list_0)):
            tile_index_0 = list_0.index(list_0[i])
            tile_index_1 = list_1.index(list_0[i])

            # Get the sum of the distance between the tile and it's goal position
            cost += abs(getRow(tile_index_0) - getRow(tile_index_1)) + abs(getCol(tile_index_0) - getCol(tile_index_1))
        return cost
    elif algorithm == 1:
        for i in range(len(list_0)):
            if list_0[i] == list_1[i]:
                cost += 1
        return len(list_0) - cost
    else:
        return 0

# State class
class State:
    def __init__(self, id, parrent_id, board, g_n, h_n, space):
        self.id = id
        self.parrent_id = parrent_id
        self.board = board
        self.g_n = g_n
        self.h_n = h_n
        self.f_n = g_n + h_n
        self.priority = g_n + h_n
        self.space = space

    def __cmp__(self, other):
        if algorithm == 0:
            return cmp(self.id, other.id)
        else:            
            return cmp(self.priority, other.priority)

# Get puzzle start and goal state input lists
start_state = raw_input("Input the start state ex.[1 2 3 ... 16]: \n").replace("[","").replace("]","").split(" ")
goal_state = raw_input("Input the goal state ex.[1 2 3 ... 16]: \n").replace("[","").replace("]","").split(" ")

# Convert the list of strings to a list of integers
start_state = map(int, start_state)
goal_state = map(int, goal_state)

# Open and closed list data structures
open_list = Queue.PriorityQueue()
closed_list = []

# Instantiate the initial state
head = State(   0, \
                None, \
                start_state, \
                0, \
                0, \
                start_state.index(0))

# Initial values
priority = 0
current_id = 0
open_list.put(head)
current_state = head
algorithm = 1

# Extra debug outpt
if debug:
    print("ID: " + str(current_id))
    print_board(current_state.board)

while current_state.board != goal_state:
    # Get the next state from the open list and add it to the closed list
    current_state = open_list.get()
    closed_list.append(current_state)

    # Extra debug outpt
    if debug:
        print("---- Current State: " + str(current_state.id) + " ---------------------")

    # Can the space move left?
    if (current_state.space - 1) >= 0 and \
        current_state.space - 1 != 3 and \
        current_state.space - 1 != 7 and \
        current_state.space - 1 != 11:
        # Increment the id number to assign to the current node
        current_id = current_id + 1

        # Swap the tiles
        temp_board = list(current_state.board)
        temp_board[current_state.space], temp_board[current_state.space - 1] = \
        temp_board[current_state.space - 1], temp_board[current_state.space]

        # Get the cost of the move based on the tile number
        if temp_board[current_state.space] < 10:
            move_cost = 1
        else:
            move_cost = 10

        # Create the leaf node for a left move
        leaf_0 = State( current_id, \
                        current_state.id, \
                        temp_board, \
                        current_state.f_n + move_cost, \
                        getCost(temp_board, goal_state, algorithm), \
                        current_state.space - 1)

        if algorithm == 0:
            leaf_0.f_n = 0

        # Extra debug outpt
        if debug:
            # Print the board after the move and wait for user input
            print("ID: " + str(current_id))
            print_board(leaf_0.board)
            print("g_n: " + str(leaf_0.g_n))
            print("h_n: " + str(leaf_0.h_n))
            print("f_n: " + str(leaf_0.f_n))
            print("")
            raw_input("")

        # If leaf's board is equal to the goal state, break out of the loop
        if(leaf_0.board == goal_state):
            break

        # Add the leaf to the open list
        open_list.put(leaf_0)

    # Can the space move right?
    if (current_state.space + 1) <= 15 and \
        current_state.space + 1 != 12 and \
        current_state.space + 1 != 8 and \
        current_state.space + 1 != 4:
        # Increment the id number to assign to the current node
        current_id = current_id + 1  

        # Swap the tiles
        temp_board = list(current_state.board)
        temp_board[current_state.space], temp_board[current_state.space + 1] = \
        temp_board[current_state.space + 1], temp_board[current_state.space]

        # Get the cost of the move based on the tile number
        if temp_board[current_state.space] < 10:
            move_cost = 1
        else:
            move_cost = 10

        # Create the leaf node for a right move
        leaf_1 = State( current_id, \
                        current_state.id, \
                        temp_board, \
                        current_state.f_n + move_cost, \
                        getCost(temp_board, goal_state, algorithm), \
                        current_state.space + 1)

        if algorithm == 0:
            leaf_1.f_n = 0

        # Extra debug outpt
        if debug:
            # Print the board after the move and wait for user input
            print("ID: " + str(current_id))
            print_board(leaf_1.board)
            print("g_n: " + str(leaf_1.g_n))
            print("h_n: " + str(leaf_1.h_n))
            print("f_n: " + str(leaf_1.f_n))
            print("")
            raw_input("")            

        # If leaf's board is equal to the goal state, break out of the loop
        if(leaf_1.board == goal_state):
            break

        # Add the leaf to the open list
        open_list.put(leaf_1)

    # Can the space move up?
    if (current_state.space - 4) > 0:
        # Increment the id number to assign to the current node
        current_id = current_id + 1

        # Swap the tiles
        temp_board = list(current_state.board)
        temp_board[current_state.space], temp_board[current_state.space - 4] = \
        temp_board[current_state.space - 4], temp_board[current_state.space]

        # Get the cost of the move based on the tile number
        if temp_board[current_state.space] < 10:
            move_cost = 1
        else:
            move_cost = 10

        # Create the leaf node for a up move
        leaf_2 = State( current_id, \
                        current_state.id, \
                        temp_board, \
                        current_state.f_n + move_cost, \
                        getCost(temp_board, goal_state, algorithm), \
                        current_state.space - 4)

        if algorithm == 0:
            leaf_2.f_n = 0

        # Extra debug outpt
        if debug:
            # Print the board after the move and wait for user input
            print("ID: " + str(current_id))
            print_board(leaf_2.board)
            print("g_n: " + str(leaf_2.g_n))
            print("h_n: " + str(leaf_2.h_n))
            print("f_n: " + str(leaf_2.f_n))
            print("")
            raw_input("")

        # If leaf's board is equal to the goal state, break out of the loop
        if(leaf_2.board == goal_state):
            break

        # Add the leaf to the open list
        open_list.put(leaf_2)

    # Can the space move down?
    if (current_state.space + 4) <= 15:
        # Increment the id number to assign to the current node
        current_id = current_id + 1

        # Swap the tiles
        temp_board = list(current_state.board)
        temp_board[current_state.space], temp_board[current_state.space + 4] = \
        temp_board[current_state.space + 4], temp_board[current_state.space]

        # Get the cost of the move based on the tile number
        if temp_board[current_state.space] < 10:
            move_cost = 1
        else:
            move_cost = 10
        
        # Create the leaf node for a down move
        leaf_3 = State( current_id, \
                        current_state.id, \
                        temp_board, \
                        current_state.f_n + move_cost, \
                        getCost(temp_board, goal_state, algorithm), \
                        current_state.space + 4)

        if algorithm == 0:
            leaf_3.f_n = 0

        # Extra debug outpt
        if debug:
            # Print the board after the move and wait for user input
            print("ID: " + str(current_id))
            print_board(leaf_3.board)
            print("g_n: " + str(leaf_3.g_n))
            print("h_n: " + str(leaf_3.h_n))
            print("f_n: " + str(leaf_3.f_n))
            print("")
            raw_input("")
        
        # If leaf's board is equal to the goal state, break out of the loop
        if(leaf_3.board == goal_state):
            break
            
        # Add the leaf to the open list
        open_list.put(leaf_3)

print_board(current_state.board)

print("Done")