def make_dcts(arr):
    dct, target_dct = {}, {}
    n = len(arr)
    for i in range(n):
        for j in range(n):
            v = arr[i][j]
            dct[v] = (i, j)
            target_dct[v] = divmod(v - 1, n) if v > 0 else (n - 1, n - 1)
    return dct, target_dct     

def get_path(from_x, from_y, target_x, target_y, avoid_x, avoid_y, n):
    seen = set([(from_x, from_y)])
    queue = [[from_x, from_y, []]]
    while queue:
        x, y, path = queue.pop(0)
        if (x, y) == (target_x, target_y):
            return path[:]
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            u, v = x + dx, y + dy
            if 0 <= u < n and 0 <= v < n and (u, v) != (avoid_x, avoid_y) and not (u, v) in seen:
                queue.append([u, v, path + [(u, v)]])
                seen.add((u, v))
                
class Puzzle:
    def __init__(self, grid):
        self.n = len(grid)
        self.dct, self.target_dct = make_dcts(grid) 
        self.order = self.get_order()
        self.step = 0
        # self.step < self.n - 3
        for x in self.order:
            print(x)


    def get_order(self):
        steps = []
        for i in range(self.n - 3):
            row = (list(range(i * self.n + i + 1, (i + 1) * self.n - 1)), [(i + 1) * self.n - 1, (i + 1) * self.n])
            col = (list(range((i + 1) * self.n + i + 1, self.n * (self.n - 2) + i + 1, self.n)), [self.n * (self.n - 2) + i + 1, self.n * (self.n - 1) + i + 1])
            steps.append([row, col])
        return steps
        
    def __str__(self):
        grid = [['##' for _ in range(self.n)] for _ in range(self.n)]
        for x, (i, j) in self.dct.items():
            grid[i][j] = x
        return '\n'.join('  '.join(map(lambda x: str(x).rjust(2, '0') if x > 0 else '##', row)) for row in grid) + "\n"
        
    def get_blank_position(self):
        for i in range(self.n):
            for j in range(self.n):
                if self.grid[i][j] == 0:
                     return (i, j)

    def get_val_at(self, i, j):
        for val, (x, y) in self.dct.items():
            if x == i and y == j:
                return val
                
    def tap(self, num):
        num_x, num_y = self.dct[num]
        blank_x, blank_y = self.dct[0]
        assert abs(num_x - blank_x) + abs(num_y - blank_y) == 1, f"{num} can't be tapped" 
        self.dct[num], self.dct[0] = self.dct[0], self.dct[num]
        print(self)
        
    def move_left(self, pos_x, pos_y):
        if pos_y == 1:
            return None
        d = -1 if pos_x == self.n - 1 else 1
        for dx, dy in ((d, 0), (d, -1), (d, -2), (0, -2), (0, -1)):
            num = self.get_val_at(pos_x + dx, pos_y + dy)
            self.tap(num)

        
    def move_fst_element_row(self):
        (fsts, lasts), _ = self.order[self.step]
        fst = fsts[0]
        fst_x, fst_y = self.dct[fst]
        tx, ty = self.target_dct[fst]
        bx, by = self.dct[0]

        # Nothing to do
        if fst_x == tx and fst_y == ty:
            return None
        elif fst_y == self.n - 1:
            path = get_path(bx, by, fst_x, fst_y - 1, fst_x, fst_y, self.n)
            for x, y in path:
                num = self.get_val_at(x, y)
                self.tap(num)
            self.tap(fst)
        else:
            path = get_path(bx, by, fst_x, fst_y + 1, fst_x, fst_y, self.n)
            for x, y in path:
                num = self.get_val_at(x, y)
                self.tap(num)
        bx, by = self.dct[0]
        for i in range(fst_y):
            self.move_left(bx, by - i)

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

p = Puzzle(g)
print(p)
p.move_fst_element_row()