# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
'''

1. N-Puzzle or sliding puzzle consists of N tiles where N can be 8, 15, 24, and so on. The puzzle is
divided into sqrt(N+1) rows and sqrt(N+1) columns. Eg. 15-Puzzle will have 4 rows and 4 columns and
an 8-Puzzle will have 3 rows and 3 columns. The puzzle consists of N tiles and one empty space where
the tiles can be moved. Possible operations include Up, Down, Left, and Right. Start and Goal
configurations (also called state) of the 8-puzzle are provided. The puzzle can be solved by moving the
tiles one by one in a single empty space and thus achieving the Goal configuration. Solve the given
problem using the following algorithms: (a) Breadth First Search Algorithm (b) Depth First Search
Algorithm and (c) A* Algorithm with a suitable heuristic.

'''

from copy import deepcopy
from os import stat
from random import shuffle
import sys
import time
import math
import heapq as heap

class solver:
    # takes the start state from user
    def __init__(self, n: int, start_state: list, goal_state: list):
        self.n = n
        self.start_state = start_state
        self.goal_state = goal_state

    # swap function to swap two matrix elements
    def swap_positions(self, matrix_deepcopy, a, b, x, y):
        matrix_deepcopy[a][b], matrix_deepcopy[x][y] = matrix_deepcopy[x][y], matrix_deepcopy[a][b]
        return matrix_deepcopy

    def give_possible_moves(self, matrix):
        # position of zero
        pos = []
        possible_moves = []
        for i in range(self.n):
            for j in range(self.n):
                # print(i,j)
                if matrix[i][j] == 0:
                    pos = [i,j]
                    break
        # left movement
        if pos[0]-1 >= 0:
            possible_moves.append(self.swap_positions(deepcopy(matrix) , pos[0], pos[1], pos[0]-1, pos[1]))
        # right movement
        if pos[0]+1 < self.n:
            possible_moves.append(self.swap_positions(deepcopy(matrix) , pos[0], pos[1], pos[0]+1, pos[1]))
        # bottom movement
        if pos[1]+1 < self.n:
            possible_moves.append(self.swap_positions(deepcopy(matrix) , pos[0], pos[1], pos[0], pos[1]+1))
        # top movement
        if pos[1]-1 >= 0:
            possible_moves.append(self.swap_positions(deepcopy(matrix) , pos[0], pos[1], pos[0], pos[1]-1))
        return possible_moves

    def manhattan_distance(self,  state: list):
        man_dist = 0
        for i in range(len(state)):
            for j in range(len(state)):
                if state[i][j] == 0:
                    continue
                i_state = state[i][j] // len(state)
                j_state = state[i][j] % len(state)
                man_dist += abs(i - i_state) + abs(j - j_state)
        return man_dist

    # convvert matrix to tuple matrix
    def give_tuple(self, matrix: list):
        return tuple(tuple(tup) for tup in matrix)

    # function to give path from start state to goal state
    def give_path(self, parent_child: dict()):
        curr_node = list(parent_child[self.give_tuple(self.goal_state)])[0]
        path = [self.goal_state]
        while curr_node != self.give_tuple(self.start_state):
            path.append(curr_node)
            curr_node = list(parent_child[curr_node])[0]
        path.append(self.start_state)
        print("path length is: ", len(path))
        print()
        time.sleep(2)
        for i in range(len(path)-1, -1, -1):
            print_state(list(path[i]))
            print() 

    # a-star solver function
    print("A* search started...\n")
    def solve_using_a_star(self, print_path: int):
        # initialize search stats
        total_pops = 0
        begin_time = time.time()
        # initialize visited set and queue
        visited = set()
        g_node = dict()
        parent_child = dict()
        queue = []
        # put start state to queue
        matrix = self.start_state
        mat_tup = self.give_tuple(matrix)
        g_node[mat_tup] = 0
        heap.heappush(queue, (self.manhattan_distance(matrix) + g_node[mat_tup],matrix))
        # starting a star search
        while len(queue) and matrix != self.goal_state:
            top_data = heap.heappop(queue)
            total_pops+=1
            matrix = list(top_data)[1]
            if matrix == self.goal_state:
                break
            visited.add(self.give_tuple(matrix))
            possible_moves = self.give_possible_moves(deepcopy(matrix) )
            # adding only those states to queue which are not visited
            for state in possible_moves:
                state_tuple = self.give_tuple(state)
                if state_tuple not in visited:
                    g_node[state_tuple] = g_node[self.give_tuple(matrix)] + 1
                    heuristic_cost = self.manhattan_distance(state)
                    total_cost = heuristic_cost + g_node[state_tuple]
                    parent_child[state_tuple] = tuple([self.give_tuple(matrix),total_cost])
                    if state_tuple in parent_child.keys():
                         if list(parent_child[state_tuple])[1] > total_cost:
                             parent_child[state_tuple] = tuple(matrix,total_cost)
                    heap.heappush(queue,(total_cost,state))
        time.sleep(1)
        end_time = time.time()
        if(matrix != self.goal_state):
            print("Goal state is unreachable.")
            return
        print("Goal state has been reached.\n")
        if(print_path):
            print("getting path...\n")
            time.sleep(2)
            self.give_path(parent_child)
        print("Total number of states viewed before solution is reached: ",total_pops)
        print(f"Total runtime of the program is {end_time - begin_time}")

# start state input from user
def get_start_state(n: int) -> list:
    start_state = []
    for i in range(n):
        # matrix input from user
        sub_matrix = list(map(int,input().split()))
        start_state.append(sub_matrix)
    return start_state

def get_random_start_state(n: int)->list:
    start_state = list(range(0,pow(n,2)))
    shuffle(start_state)
    new_state = []
    i = 0
    while(i < pow(2,n)):
        j = 0
        sub_matrix = []
        while(j < n):
            sub_matrix.append(start_state[i])
            j+=1
            i+=1
        new_state.append(sub_matrix)
    return new_state

# goal state input from user
def get_goal_state(n: int) -> list:
    goal_state = []
    i = 0
    while(i < pow(2,n)):
        j = 0
        sub_matrix = []
        while(j < n):
            sub_matrix.append(i)
            j+=1
            i+=1
        goal_state.append(sub_matrix)
    return goal_state

# print state matrix
def print_state(matrix: list):
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            print(matrix[i][j], end = ' ')
        print()

if __name__ == "__main__":
    n = 8
    random = 0
    print_path = 0
    n = int(math.ceil(math.sqrt(n+1)))
    if(random == 1):
        start_state = get_random_start_state(n)
    # start state given in question
    else:
        start_state =[[7,2,4],[5,0,6],[8,3,1]]
    goal_state = get_goal_state(n)
    goal_state = get_goal_state(n)
    print("start_state: \n")
    print_state(start_state)
    print()
    print("goal_state: \n")
    print_state(goal_state)
    print()
    if n > 3 and random == 0:
        print("Goal and start state does not have "+ str(n*n - 1) +" elements")
    else:
        solver_obj = solver(n, start_state, goal_state)
        solver_obj.solve_using_a_star(print_path)