#!/usr/bin/python3

import random

initial_position =  [ ' 1', ' 2', ' 3', ' 4',
                      ' 5', ' 6', ' 7', ' 8',
                      ' 9', '10', '11', '12', 
                      '13', '14', '15', '  ' ]

def display(cells):
    for i in range(0,16):
        if i % 4 == 0:
            print('+--+--+--+--+')
            print('|' + cells[i] + '|' + cells[i+1] + '|' + cells[i+2] + '|' + cells[i+3] + '|')
    print('+--+--+--+--+')

def find(cells, s):
    for i in range(0, 16):
        if cells[i].strip() == s.strip():
            return i
    return -1

def nsew_pos(pos):
    res = []
    x = pos % 4
    y = pos // 4
    if x > 0:
        res.append(pos - 1)
    if x < 3:
        res.append(pos + 1)
    if y > 0:
        res.append(pos - 4)
    if y < 3:
        res.append(pos + 4)
    return res

def equal_to_initial_position(cells):
    for i in range(0, 16):
        if cells[i] != initial_position[i]:
            return False
    return True

def switch(cells, pos):
    x = find(cells,pos)
    if x < 0:
        print('invalid cell')
    else:
        y = find(cells,'  ')
        if y in nsew_pos(x):
            cells[x], cells[y] = cells[y], cells[x]

cells = []                      # initialize the state of the game
cells += initial_position
random.shuffle(cells)           # shuffle
while not equal_to_initial_position(cells):
    display(cells)
    pos = input('switch? ')
    switch(cells,pos)