from collections import deque
def from_hash(st):
    return [list(map(int, r.split(','))) for r in st.split(';')]

def hash(board):
    return ';'.join(','.join(str(x) for x in r) for r in board)

def show(board):
    return '\n'.join(' '.join(str(x).rjust(2, '0') for x in r) for r in board)  + '\n\n'
    
class Puzzle:
    def __init__(self, board):
        self.board = board
        self.n = len(board)
        self.pos = {}
        for i in range(self.n):
            for j in range(self.n):
                self.pos[board[i][j]] = (i, j)

    def copy(self):
        return Solver(self.board)
        
    def get_position(self, v):
        return self.pos[v]

    def swap(self, p, q):        
        px, py = p
        qx, qy = q
        vp, vq = self.board[px][py], self.board[qx][qy]
        assert vp == 0 or vq == 0, "Impossible swapping"
        self.board[px][py], self.board[qx][qy] = self.board[qx][qy], self.board[px][py]
        self.pos[vp], self.pos[vq] = q, p
        

    def make_moves(self, move_lst):
        for p, q in zip(move_lst, move_lst[1:]):
            self.swap(p, q)

        
    def bfs(self, val, target, obstacles):
        tx, ty = target
        h = hash(self.board)
        ox, oy = self.get_position(0)

        seen = set([h])
        q = deque([(h, (ox, oy), [(ox, oy)])])
        print(q)
        while len(q) > 0:
            board_str, pos, path = q.popleft()
            board = from_hash(board_str)
            if board[tx][ty] == val:
                
                return path
            x, y = pos
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                u, v = x + dx, y + dy
                if 0 <= u < self.n and 0 <= v < self.n and not (u, v) in obstacles:
                    cpy = [r[:] for r in board]
                    cpy[x][y], cpy[u][v] = cpy[u][v], cpy[x][y]
                    _h = hash(cpy)
                    if not _h in seen:
                        seen.add(_h)
                        q.append((_h, (u, v), path + [(u, v)]))
                    
    def solve(self):
        ans = []
        step = 0
        obs = set()

        moves = self.bfs(21, (self.n - 2, self.n - 1), obs)
        self.make_moves(moves)
        print(show(self.board)) 

        return 
        for col in range(self.n - 2):
            moves = self.bfs(step * self.n + col + 1, (step, col), obs)
            self.make_moves(moves)
            obs.add((step, col))
            print(show(self.board))
        
        moves = self.bfs((step + 1) * self.n - 1, (step, self.n - 1), obs)
        self.make_moves(moves)
        print(show(self.board))


        moves = self.bfs((step + 1) * self.n, (step + 1, (step + 1) * self.n - 1), obs)
        self.make_moves(moves)
        print(show(self.board))
        obs.add((step + 1, (step + 1) * self.n - 1))
        
        moves = self.bfs(0, (step + 1, (step + 1) * self.n - 2), obs)
        self.make_moves(moves)
        print(show(self.board))
        
        self.make_moves([(step + 1, (step + 1) * self.n - 2), (step, (step + 1) * self.n - 2),
                         (step, (step + 1) * self.n - 1), (step + 1, (step + 1) * self.n - 1)])
        obs.remove((step + 1, (step + 1) * self.n - 1))
        obs.add((step, self.n - 2))
        obs.add((step, self.n - 1))
        print(show(self.board))
        #########################################
        for row in range(step + 1, self.n - 2):
            moves = self.bfs(row * self.n + step + 1, (row, step), obs)
            self.make_moves(moves)
            obs.add((row, step))
            print(show(self.board))

        # moves = self.bfs((self.n - 1) * self.n + step + 1, (self.n - 1, 2), obs)
        # self.make_moves(moves)
        # print(show(self.board))            

        
        # moves = self.bfs((self.n - 1) * self.n + step + 1, (self.n - 1, step), obs)
        # self.make_moves(moves)
        # print(show(self.board))
        # obs.add((self.n - 1, step))

        # moves = self.bfs((self.n - 1) * self.n + step + 1, (self.n - 1, step + 1), obs)
        # self.make_moves(moves)
        # print(show(self.board))
        # obs.add((self.n - 1, step + 1))

        # moves = self.bfs(0, (self.n - 2, step + 1), obs)
        # self.make_moves(moves)
        # print(show(self.board))
        # self.make_moves([(step + 1, (step + 1) * self.n - 2), (step, (step + 1) * self.n - 2),
        #                  (step, (step + 1) * self.n - 1), (step + 1, (step + 1) * self.n - 1)])
        # obs.remove((step + 1, (step + 1) * self.n - 1))
        # obs.add((self.n - 2, step))
        # print(show(self.board))

        
board = [
	[ 3, 7,14,15,10],
	[ 1, 0, 5, 9, 4],
	[16, 2,11,12, 8],
	[17, 6,13,18,20],
	[21,22,23,19,24]
]

board = [[1, 2 ,3, 4 ,5],
[6, 7, 15, 10, 8],
[11, 0, 13,9, 12],
[14 ,16, 17, 18, 20],
[21, 22, 23 ,19 ,24]]

p = Puzzle(board) 
p.solve()