m = 3
n = 3

def swap(board,i,j,k,l):
    tmp = board[i][j]
    board[i][j] = board[k][l]
    board[k][l] = tmp
    return board

def copy(board):
    ret = [[0 for x in range(n)] for y in range(m)]
    for i in range(m):
        for j in range(n):
            ret[i][j] = board[i][j]
    return ret

def unique_string(board):
    if (board == None):
        return ""
    s = ""
    if (board == None):
        return s
    for i in range(m):
        for j in range(n):
            s += str(board[i][j])
    return s

def find_zero(board):
    for i in range (m):
        for j in range (n):
            if (board[i][j] == 0):
                return (i, j)

def verify_goal_state(array):
    goal = 0
    for i in range (m):
        for j in range (n):
            if (array[i][j] == goal):
                goal = goal + 1
            else: return False
    return True

def move_up(original_board):
    board = copy(original_board)
    zero_position = find_zero(board)
    if (zero_position[0] == 0):
        return None

    else:
        i = zero_position[0]
        j = zero_position[1]
        k = i - 1
        l = j
        swap(board,i,j,k,l)
    return board

#array = [[3,1,2],[0,4,5],[6,7,8]]
#move_up(array)

def move_down(original_board):
    board = copy(original_board)
    zero_position = find_zero(board)
    if (zero_position[0] == 2):
        return None

    else:
        i = zero_position[0]
        j = zero_position[1]
        k = i + 1
        l = j
        swap(board,i,j,k,l)
    return board

array = [[0,1,2],[3,4,5],[6,7,8]]
move_down(array)

def move_right(original_board):
    board = copy(original_board)
    zero_position = find_zero(board)
    if (zero_position[1] == 2):
        return None

    else:
        i = zero_position[0]
        j = zero_position[1]
        k = i
        l = j + 1
        swap(board,i,j,k,l)
    return board

#array = [[2,0,1],[3,4,5],[6,7,8]]
#move_Right(array)

def move_left(original_board):
    board = copy(original_board)
    zero_position = find_zero(board)
    if (zero_position[1] == 0):
        return None

    else:
        i = zero_position[0]
        j = zero_position[1]
        k = i
        l = j - 1
        swap(board,i,j,k,l)
    return board

visited_state = set("")
goal_found = False
def ids(board):
    global visited_state
    global goal_found

    queue = []
    max_depth = 0

    queue.append(board)
    while (len(queue) > 0 and goal_found != True):
        for current_board in queue:
            current_board = queue.pop(0)
            current_state = unique_string(current_board)
            if (current_state not in visited_state):
                result = dfs(current_board, 0, max_depth, queue)
                max_depth += 1
                if (result != None):
                    visited_state = set()
                    goal_found = False
                    return result


def dfs(board, current_depth, max_depth, queue):

    result = None
    if (current_depth <= max_depth):
        global visited_state
        global goal_found
        state = unique_string(board)
        if (goal_found == False and board != None and state not in visited_state):
#             print_result(board)

            if (verify_goal_state(board)):
                goal_found = True
                return board

            visited_state.add(state)

            state1 = move_up(board)
            state2 = move_down(board)
            state3 = move_left(board)
            state4 = move_right(board)

            result = dfs(state1, current_depth + 1, max_depth, queue)
            if (result == None):
                result = dfs(state2, current_depth + 1, max_depth, queue)
            if (result == None):
                result = dfs(state3, current_depth + 1, max_depth, queue)
            if (result == None):
                result = dfs(state4, current_depth + 1, max_depth, queue)

    queue.append(board)
    return result

class MyHeap:
    def __init__(self):
        self.heapList = [[]]
        self.currentSize = 0

    def percUp(self,i):
        while i // 2 > 0:
          if self.heapList[i].h < self.heapList[i // 2].h:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
          i = i // 2

    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)

    def percDown(self,i):
      while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i].h > self.heapList[mc].h:
              tmp = self.heapList[i]
              self.heapList[i] = self.heapList[mc]
              self.heapList[mc] = tmp
          i = mc

    def minChild(self,i):
      if i * 2 + 1 > self.currentSize:
          return i * 2
      else:
          if self.heapList[i*2].h < self.heapList[i*2+1].h:
              return i * 2
          else:
              return i * 2 + 1

    def delMin(self):
      retval = self.heapList[1]
      self.heapList[1] = self.heapList[self.currentSize]
      self.currentSize = self.currentSize - 1
      self.heapList.pop()
      self.percDown(1)
      return retval

    def buildHeap(self,alist):
      i = len(alist) // 2
      self.currentSize = len(alist)
      self.heapList = [0] + alist[:]
      while (i > 0):
          self.percDown(i)
          i = i - 1

class MyBoard:
    def __init__(self, board, value):
        self.board = board
        self.h = value


def h(board):
    result = 0
    goal = 0
    for i in range(m):
        for j in range(n):
            result += abs(goal - board[i][j])
            goal += 1
    return result
# array = [[2,0,1],[3,4,5],[6,7,8]]
# print(h(array))

def A_Star_Search(original_board):
    heuristic_function = h

    goal_found = False
    visited_states = set("")
    working_states = set("")
    next_states = MyHeap()

    first_board = MyBoard(original_board, heuristic_function(original_board))
    next_states.insert(first_board)

    number_of_interations = 0;
    while(next_states.currentSize > 0 and goal_found == False):
        number_of_interations += 1
        current_state = next_states.delMin()
        current_state_string = unique_string(current_state.board)

        if (verify_goal_state(current_state.board)):
            goal_found = True
            print("Goal has been found:")
            print(current_state.board)
            print("number Of interation: " + str(number_of_interations))
            return

        if (current_state_string not in visited_states):
            state1 = move_up(current_state.board)
            state2 = move_down(current_state.board)
            state3 = move_left(current_state.board)
            state4 = move_right(current_state.board)

            # print("possible next states:")
            # print(state1)
            # print(state2)
            # print(state3)
            # print(state4)

            state1_string = unique_string(state1)
            if (state1 != None and state1_string not in working_states):
                next_states.insert(MyBoard(state1, heuristic_function(state1)))
                working_states.add(state1_string)

            state2_string = unique_string(state2)
            if (state2 != None and state2_string not in working_states):
                next_states.insert(MyBoard(state2, heuristic_function(state2)))
                working_states.add(state2_string)

            state3_string = unique_string(state3)
            if (state3 != None and state3_string not in working_states):
                next_states.insert(MyBoard(state3, heuristic_function(state3)))
                working_states.add(state3_string)

            state4_string = unique_string(state4)
            if (state4 != None and state4_string not in working_states):
                next_states.insert(MyBoard(state4, heuristic_function(state4)))
                working_states.add(state4_string)

        visited_states.add(current_state_string)


board1 = [[1,2,0],[3,4,5],[6,7,8]]
board2 = [[4, 2, 5], [7, 3, 1], [6, 8, 0]]
board3 = [[4, 2, 5], [7, 3, 1], [6, 0, 8]]

import time
current_milli_time = lambda: int(round(time.time() * 1000))

start_time = current_milli_time()
A_Star_Search(board3)
end_time = current_milli_time()
print("A Star question 2 Run Time: " + str(end_time - start_time) + "(ms)")

start_time = current_milli_time()
ids(board3)
end_time = current_milli_time()
print("IDS Run Time: " + str(end_time - start_time) + "(ms)")