from heapq import heappush,heappop
import sys
import random

# Как это работает:
# - доска кодируется массивом из 16 чисел 1..16, где 16 означает пустое
# место (глупо, надо переделать на 0). Индексы массива 0..15.
# - состояние доски включает в себя также "замороженные" индексы, которые мы
# не хотим больше двигать.
# главная функция board.moveto(val, to) находит способ передвинуть костяшку
# номер val с ее текущего места на индекс номер to. Чтобы найти такой пусть,
# мы рассматриваем доску как граф, в котором замороженные вершины-индексы удаляем.
# Среди оставшихся находим самый быстрый путь алгоритмом Дайкстры. Теперь, когда
# мы его нашли, мы хотим собственно двигать костяшку по этому пути, и для каждого
# ее шага сначала находим пусть для 16 (пустого места) встать на следующий шаг в пути
# (это еще один Дайкстра, только ведомая костяшка тоже заморожена) и потом обменяться
# с ведомой костяшкой. Потом опять позиционируем пустышку, и так далее.
# Все это будет работать кроме тех случаев, когда вложенный Дайкстра для пустышки не
# может найти путь, потому что граф рассоединился. Это то, что происходит в знакомой
# ситуации, когда 1,2,3 уже стоят на месте, а 4 придвинулся к своему, но не может встать,
# не потревожив 1,2,3. Для таких случаев у нас есть две hardcoded последовательности,
# для угловой по горизонтали или по вертикали.
# Мы расставляем костяшки в порядке 1-8, потом 9,13 (в этом порядке), 10, 14, 11 и
# пустышку в угол, теперь либо все в порядке, либо 12/15 поменяны местами.

# Returns the set of the 2-4 neighbours of board cell n
def neighbors(n):
  s = set(i for i in [n+4,n-4] if i >= 0 and i < 16)
  next = set([n+1]) if n % 4 != 3 else set()
  prev = set([n-1]) if n % 4 != 0 else set()
  return s | next | prev

# Finds the shortest distance path. Assumes
# vertices are 0..15 except those in the set 'frozen'.
def dijkstra(fr, to, frozen):
  h = []
  heappush(h, (0,fr))
  final_edge = {}
  visited = set()
  while h:
    (d, v) = heappop(h)
    if v in visited:
      continue
    visited.add(v)
    if v == to:
      break
    for n in neighbors(v) - frozen - visited:
      heappush(h, (d+1, n))
      if n not in final_edge or final_edge[n][1] > d:
        final_edge[n] = v, d
        # print "final_edge from: ", v, " to: ", n, " for distance: ", d
  if to not in final_edge:
    return []
  moves = [to]
  v = to
  while v != fr:
    (v, d) = final_edge[v]
    moves.append(v)
  return list(reversed(moves))

class board:
  def __init__(self, randomize=False):
    self.arr = [i+1 for i in range(0,16)]
    self.inv = [i-1 for i in range(0,17)]
    self.moves = []
    self.frozen = set()
    if randomize:
      random.shuffle(self.arr)
    for (k,v) in enumerate(self.arr):
      self.inv[v] = k
  def at(self, i): return self.arr[i]
  def where(self, n): return self.inv[n]
  def show(self):
    for i in range(0,16):
      sys.stdout.write('%2d ' % self.arr[i])
      if i % 4 == 3:
        print ""

  # Makes a puzzle move. n must be a cell adjacent to the blank.
  def move(self, n):
    blanks = [i for i in neighbors(n) if self.arr[i]==16]
    if len(blanks) != 1:
      raise Exception('Invalid move at: ' + str(n))
    val = self.arr[n]
    self.arr[n], self.arr[blanks[0]] = 16, val
    self.inv[val], self.inv[16] = blanks[0], n
    self.moves.append(n)

  # Execute given moves and add them to the list.
  def execute(self, new_moves):
    for n in new_moves:
      self.move(n)
    self.moves.extend(new_moves)

  # Position the blank in a wanted location. Returns true/false if
  # successful/impossible.
  def moveblank(self, to, frozen=None):
    if frozen is None:
      frozen = self.frozen
    if self.where(16) != to:
      path = dijkstra(self.where(16), to, frozen)
      if not path:
        return False
      self.execute(path[1:])
    return True

  # Move value val to cell to, freeze cell to.
  def moveto(self, val, to):
    # print "---moving val %d from %d to %d" % (val, self.where(val), to)
    # print self.frozen
    fr = self.where(val)
    if fr == to:
      self.frozen.add(to)
      return
    # first find a path through non-frozen cells
    path = dijkstra(fr, to, self.frozen)
    if not path:
      raise Exception('Path not found')
    # For each path step except last, position the blank there and make the move
    cur = fr  # current location of the moving piece
    for p in path[1:-1]:
      self.moveblank(p, self.frozen | set([cur]))
      self.execute([cur])
      cur = p
    # We're at the final step. Can we move the blank there?
    if self.moveblank(path[-1], self.frozen | set([cur])):
      self.execute([cur])
    else:
      # We must be at a right or bottom edge.
      if cur == path[-1]+4:  # right edge
        self.moveblank(cur+4, self.frozen | set([cur]))
        self.execute([cur, cur-4, cur-5, cur-1, cur, cur+4, cur+3, cur-1, cur-5, cur-4, cur])
      elif cur == path[-1]+1:  # bottom edge
        self.moveblank(cur+1, self.frozen | set([cur]))
        self.execute([cur, cur-1, cur-5, cur-4, cur, cur+1, cur-3, cur-4, cur-5, cur-1, cur])
      else:
        raise Exception('Unable to perform final step')
    self.frozen.add(to)
    # print "---done moving val %d" % val

def solve_board(board):
  for piece in [1,2,3,4,5,6,7,8,9,13,10,14]:
    board.moveto(piece, piece-1)
  board.moveto(11, 10)
  board.moveblank(15)
  # board.show()
  return

solvable = 0
unsolvable = 0
for i in range(0,1000):
  b = board(True)
  solve_board(b)
  for i in [0,1,2,3,4,5,6,7,8,9,10,12,13]:
    if b.at(i) != i+1:
      raise Exception('Unsolved')
  if b.at(11) == 12:
    solvable += 1
  else:
    unsolvable += 1
print "solvable: %d unsolvable: %d" % (solvable, unsolvable)