Untitled

import sys
from random import randint
from heapq import heappop, heappush

COLUMNS = 4
ROWS = 3

dist = [[abs(t // COLUMNS - s // COLUMNS) + abs(t % COLUMNS - s % COLUMNS) if s > 0 else 0
    for t in range(ROWS * COLUMNS)]
        for s in range(ROWS * COLUMNS)]

def compute_empty_position(grid):
    for i, v in enumerate(grid):
        if v == 0:
            return i

def heuristic(grid):
    return sum(dist[rv][index] for index, rv in enumerate(grid))

class Node(object):
    def __init__(self, grid, actions, empty_position, h, last=None):
        self.grid = grid
        self.actions = actions
        self.h = h
        self.dist = len(self.actions) + h
        self.last = last
        self.empty_position = empty_position

    def neighboors(self):
        possibilities = []
        i = self.empty_position
        col = i % COLUMNS
        if col + 1 < COLUMNS and self.last != 2:
            possibilities.append((i + 1, 1))
        if col > 0 and self.last != 1:
            possibilities.append((i - 1, 2))
        if i < (ROWS - 1) * COLUMNS and self.last != 4:
            possibilities.append((i + COLUMNS, 3))
        if i >= COLUMNS and self.last != 3:
            possibilities.append((i - COLUMNS, 4))

        for action, move in possibilities:
            before = dist[self.grid[i]][i] + dist[self.grid[action]][action]

            new_grid = list(self.grid)
            new_grid[i], new_grid[action] = new_grid[action], new_grid[i]
            new_grid = tuple(new_grid)

            after = dist[new_grid[i]][i] + dist[new_grid[action]][action]

            yield Node(new_grid, self.actions + [action], action, self.h - before + after, move)

    def __lt__(self, other):
        return self.dist < other.dist

def solve(grid):
    orig = grid[:]
    visited = set()
    q = [Node(orig, [], compute_empty_position(orig), heuristic(orig))]
    while q:
        node = heappop(q)
        visited.add(node.grid)
        if node.h == 0:
            return node.actions
        for n in node.neighboors():
            if n.grid not in visited:
                heappush(q, n)
    print("no solution found!")

if __name__ == '__main__':
    grid = tuple(int(x) for _ in range(ROWS) for x in input().split(" "))
    res = solve(grid)
    for action in res:
        print(action // COLUMNS, action % COLUMNS)