O 15 Puzzle é um quebra-cabeça famoso que envolve deslizar 15 peças em uma grade 4x4. A partir de uma configuração aleatória, o objetivo é organizar os blocos na ordem correta. Aqui está um exemplo de um quebra-cabeça 15 resolvido:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15

Cada movimento no quebra-cabeça tem a forma Cima / Baixo / Esquerda / Direita. O movimento "Para baixo" consiste em deslizar o ladrilho que está acima do ponto vazio para baixo. O movimento "Direito" consiste em deslizar um ladrilho para a direita, no local vazio. Aqui está como o quadro cuida dos movimentos Para baixo e para a direita.

01 02 03 04
05 06 07 08
09 10    11
13 14 15 12

O objetivo deste desafio é escrever um programa que possa gerar a série de movimentos necessários para resolver o 15 Puzzle. O vencedor é o programa que resolve os cinco casos de teste (abaixo) no menor número de movimentos. A solução gerada não precisa ser uma solução perfeita, apenas precisa ser melhor que a dos concorrentes. Para cada caso de teste individual, o programa não deve demorar mais de dez segundos em uma máquina razoável.

Seu programa deve ser capaz de resolver qualquer quebra-cabeça que possa ser solucionado. Estou apenas usando esses cinco casos de teste como pontuação.

Seu programa receberá o 15 Puzzle não resolvido como entrada no formato de uma matriz 2D. A matriz 2D pode ser formatada de acordo com o idioma usado ou alterada se o idioma não tiver matrizes 2D. O primeiro elemento do primeiro subconjunto será o número no canto superior esquerdo e o último elemento do primeiro subconjunto será o número no canto superior direito. A 0será o espaço vazio.

Como saída, seu programa deve imprimir uma lista de movimentos na ordem em que eles precisam ser executados. Cada etapa deve ser numerada para aumentar a usabilidade dos resultados.

EDIT: Com base nos comentários, permitirei que a saída seja na forma de Down / Up / etc ou na forma das coordenadas da peça a serem movidas. Como este não é um código de golfe, a parte mais importante é resolver o quebra-cabeça.

Algumas outras regras gerais não envolvem o uso de uma fonte externa, etc.

Caso de teste 1

([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])

Saída de exemplo:

1: Down
2: Down
3: Down
4: Left
....

Caso de teste 2

([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])

Caso de teste 3

([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])

Caso de teste 4

([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])

Caso de teste 5

([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])

PyPy, 195 movimentos, ~ 12 segundos de computação

Calcula soluções ideais usando o IDA * com uma heurística de "curta distância" aumentada por conflitos lineares. Aqui estão as soluções ideais:

 5  1  7  3
 9  2 11  4
13  6 15  8
 0 10 14 12
Down, Down, Down, Left, Up, Up, Up, Left, Down, Down, Down, Left, Up, Up, Up

 2  5 13 12
 1  0  3 15
 9  7 14  6
10 11  8  4
Left, Down, Right, Up, Up, Left, Down, Down, Right, Up, Left, Left, Down, Right, Right, Right, Up, Up, Left, Left, Down, Left, Up, Up, Right, Down, Down, Left, Up, Up, Right, Right, Right, Down, Left, Up, Right, Down, Down, Left, Left, Down, Left, Up, Up, Right, Up, Left

 5  2  4  8
10  0  3 14
13  6 11 12
 1 15  9  7
Left, Up, Up, Right, Right, Down, Left, Up, Left, Left, Down, Down, Right, Right, Up, Left, Left, Down, Down, Right, Right, Up, Right, Up, Left, Left, Up, Right, Down, Down, Right, Down, Left, Left, Up, Up, Left, Up

11  4 12  2
 5 10  3 15
14  1  6  7
 0  9  8 13
Down, Left, Down, Right, Up, Left, Left, Left, Down, Down, Right, Right, Right, Up, Left, Left, Left, Down, Right, Right, Up, Left, Up, Up, Left, Down, Down, Right, Down, Right, Up, Up, Right, Up, Left, Left, Left, Down, Right, Right, Right, Up, Left, Down, Left, Down, Left, Up, Up

 5  8  7 11
 1  6 12  2
 9  0 13 10
14  3  4 15
Up, Right, Down, Left, Left, Down, Left, Up, Right, Up, Right, Down, Down, Right, Up, Up, Left, Left, Left, Down, Down, Down, Right, Right, Up, Right, Down, Left, Up, Left, Up, Left, Down, Right, Down, Left, Up, Right, Down, Right, Up, Up, Left, Left, Up

E o código:

import random


class IDAStar:
    def __init__(self, h, neighbours):
        """ Iterative-deepening A* search.

        h(n) is the heuristic that gives the cost between node n and the goal node. It must be admissable, meaning that h(n) MUST NEVER OVERSTIMATE the true cost. Underestimating is fine.

        neighbours(n) is an iterable giving a pair (cost, node, descr) for each node neighbouring n
        IN ASCENDING ORDER OF COST. descr is not used in the computation but can be used to
        efficiently store information about the path edges (e.g. up/left/right/down for grids).
        """

        self.h = h
        self.neighbours = neighbours
        self.FOUND = object()


    def solve(self, root, is_goal, max_cost=None):
        """ Returns the shortest path between the root and a given goal, as well as the total cost.
        If the cost exceeds a given max_cost, the function returns None. If you do not give a
        maximum cost the solver will never return for unsolvable instances."""

        self.is_goal = is_goal
        self.path = [root]
        self.is_in_path = {root}
        self.path_descrs = []
        self.nodes_evaluated = 0

        bound = self.h(root)

        while True:
            t = self._search(0, bound)
            if t is self.FOUND: return self.path, self.path_descrs, bound, self.nodes_evaluated
            if t is None: return None
            bound = t

    def _search(self, g, bound):
        self.nodes_evaluated += 1

        node = self.path[-1]
        f = g + self.h(node)
        if f > bound: return f
        if self.is_goal(node): return self.FOUND

        m = None # Lower bound on cost.
        for cost, n, descr in self.neighbours(node):
            if n in self.is_in_path: continue

            self.path.append(n)
            self.is_in_path.add(n)
            self.path_descrs.append(descr)
            t = self._search(g + cost, bound)

            if t == self.FOUND: return self.FOUND
            if m is None or (t is not None and t < m): m = t

            self.path.pop()
            self.path_descrs.pop()
            self.is_in_path.remove(n)

        return m


def slide_solved_state(n):
    return tuple(i % (n*n) for i in range(1, n*n+1))

def slide_randomize(p, neighbours):
    for _ in range(len(p) ** 2):
        _, p, _ = random.choice(list(neighbours(p)))
    return p

def slide_neighbours(n):
    movelist = []
    for gap in range(n*n):
        x, y = gap % n, gap // n
        moves = []
        if x > 0: moves.append(-1)    # Move the gap left.
        if x < n-1: moves.append(+1)  # Move the gap right.
        if y > 0: moves.append(-n)    # Move the gap up.
        if y < n-1: moves.append(+n)  # Move the gap down.
        movelist.append(moves)

    def neighbours(p):
        gap = p.index(0)
        l = list(p)

        for m in movelist[gap]:
            l[gap] = l[gap + m]
            l[gap + m] = 0
            yield (1, tuple(l), (l[gap], m))
            l[gap + m] = l[gap]
            l[gap] = 0

    return neighbours

def slide_print(p):
    n = int(round(len(p) ** 0.5))
    l = len(str(n*n))
    for i in range(0, len(p), n):
        print(" ".join("{:>{}}".format(x, l) for x in p[i:i+n]))

def encode_cfg(cfg, n):
    r = 0
    b = n.bit_length()
    for i in range(len(cfg)):
        r |= cfg[i] << (b*i)
    return r


def gen_wd_table(n):
    goal = [[0] * i + [n] + [0] * (n - 1 - i) for i in range(n)]
    goal[-1][-1] = n - 1
    goal = tuple(sum(goal, []))

    table = {}
    to_visit = [(goal, 0, n-1)]
    while to_visit:
        cfg, cost, e = to_visit.pop(0)
        enccfg = encode_cfg(cfg, n)
        if enccfg in table: continue
        table[enccfg] = cost

        for d in [-1, 1]:
            if 0 <= e + d < n:
                for c in range(n):
                    if cfg[n*(e+d) + c] > 0:
                        ncfg = list(cfg)
                        ncfg[n*(e+d) + c] -= 1
                        ncfg[n*e + c] += 1
                        to_visit.append((tuple(ncfg), cost + 1, e+d))

    return table

def slide_wd(n, goal):
    wd = gen_wd_table(n)
    goals = {i : goal.index(i) for i in goal}
    b = n.bit_length()

    def h(p):
        ht = 0 # Walking distance between rows.
        vt = 0 # Walking distance between columns.
        d = 0
        for i, c in enumerate(p):
            if c == 0: continue
            g = goals[c]
            xi, yi = i % n, i // n
            xg, yg = g % n, g // n
            ht += 1 << (b*(n*yi+yg))
            vt += 1 << (b*(n*xi+xg))

            if yg == yi:
                for k in range(i + 1, i - i%n + n): # Until end of row.
                    if p[k] and goals[p[k]] // n == yi and goals[p[k]] < g:
                        d += 2

            if xg == xi:
                for k in range(i + n, n * n, n): # Until end of column.
                    if p[k] and goals[p[k]] % n == xi and goals[p[k]] < g:
                        d += 2

        d += wd[ht] + wd[vt]

        return d
    return h




if __name__ == "__main__":
    solved_state = slide_solved_state(4)
    neighbours = slide_neighbours(4)
    is_goal = lambda p: p == solved_state

    tests = [
        (5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12),
        (2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4),
        (5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7),
        (11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13),
        (5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15),
    ]

    slide_solver = IDAStar(slide_wd(4, solved_state), neighbours)

    for p in tests:
        path, moves, cost, num_eval = slide_solver.solve(p, is_goal, 80)
        slide_print(p)
        print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))
        print(cost, num_eval)

Etapas totais de JavaScript (ES6) 329 para todos os 5 casos de teste em ~ 1min

Editar Mesma estratégia, diferentes alvos, melhor solução. Mais devagar ...

É mais ou menos assim que eu resolvo isso manualmente: usando alvos intermediários Depois de cada alvo, os blocos relativos não são movidos novamente. Cada alvo intermediário é alcançado usando uma função BSF paramétrica. Os 2 parâmetros são a condição do loop L (repita enquanto verdadeiro) e a condição de seleção S (selecione o bloco que pode ser movido). Os passos:

1. Coloque 1 superior / esquerda
2. Lugar 2
3. Lugar 5
4. Lugar 3,4 - linha superior ok
5. Lugar 9,13 - coluna esquerda ok
6. Todo o resto

Nota lateral : Não checo a posição dos ladrilhos 14 e 15. Quebra-cabeças insolúveis, como [11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]o 14 e o 15, foram trocados.

F=b=>(
  s=[],
  [[_=>b[0]!=1, (o,p)=>b[o+p]]
  ,[_=>b[1]!=2, (o,p)=>(p=b[o+p])>1&&p]
  ,[_=>b[5]!=5, (o,p)=>(p=b[o+p])>2&&p]
  ,[_=>b[2]!=3|b[3]!=4, (o,p)=>(p=b[o+p])>2&&p!=5&&p]
  ,[_=>b[10]!=9|b[15]!=13, (o,p)=>(p=b[o+p])>5&&p]
  ,[_=>b[6]!=6|b[7]!=7|b[8]!=8|b[11]!=10|b[12]!=11|b[13]!=12|b[18]!=0, (o,p)=>(p=b[o+p])>5&&p!=9&&p!=13&&p]
  ].forEach(([L,S])=>{
    for(v={},v[b]=1,t=0,m=[];L();)
    {
      b.forEach((x,p)=>
        x=='0'&&[-1,5,1,-5].forEach((o,d)=>
          (x=S(o,p))&&(c=b.slice(0),c[p]=x,c[o+p]=0,v[k=''+c]?0:v[k]=m.push([c,s.concat(d)]))
        )
      );[b,s]=m[t++]
    }
  }),
  ,s.map((d,i)=>i+': '+'RULD'[d]).join('\n') // multi line output
  // ,s.map(d=>'RULD'[d]).join(' ') // single line output (easier to test)
)

Snippet aberto para testar ou reproduzir (apenas Firefox)

F=b=>(
  s=[],
  [[_=>b[0]!=1, (o,p)=>b[o+p]]
  ,[_=>b[1]!=2, (o,p)=>(p=b[o+p])>1&&p]
  ,[_=>b[5]!=5, (o,p)=>(p=b[o+p])>2&&p]
  ,[_=>b[2]!=3|b[3]!=4, (o,p)=>(p=b[o+p])>2&&p!=5&&p]
  ,[_=>b[10]!=9|b[15]!=13, (o,p)=>(p=b[o+p])>5&&p]
  ,[_=>b[6]!=6|b[7]!=7|b[8]!=8|b[11]!=10|b[12]!=11|b[13]!=12|b[18]!=0, (o,p)=>(p=b[o+p])>5&&p!=9&&p!=13&&p]
  ].forEach(([L,S])=>{
    for(v={},v[b]=1,t=0,m=[];L();)
    {
      b.forEach((x,p)=>
        x=='0'&&[-1,5,1,-5].forEach((o,d)=>
          (x=S(o,p))&&(c=b.slice(0),c[p]=x,c[o+p]=0,v[k=''+c]?0:v[k]=m.push([c,s.concat(d)]))
        )
      );[b,s]=m[t++]
    }
  }),
  //,s.map((d,i)=>i+': '+'RULD'[d]).join('\n') // multi line output
  //,s.map(d=>'RULD'[d]).join(' ') // single line output (easier to test)
  s
)
B.value=PZ.value,show()

function show(s='') {
  var b = eval(B.value)
  var t = b.map((c,i)=>'<td>'+c+'</td>').join()
  .replace(/,,/g,'</tr><tr>').replace(/,/g,'')
  G.innerHTML='<tr>'+t+'</tr>'
  S.value=s
}
function solve() {
  show('... solving ...')
  var b = eval(B.value)
  setTimeout(_=>{
    var s = F(b), zp = b.indexOf(0), sp = 0
    S.value=s.map(d=>'RULD'[d]).join(' ');
    (A=_=>{
      d=[-1,5,1,-5][m=s[sp++]]
      b[zp]=b[zp+d],zp+=d,b[zp]=0
      var t = b.map((c,i)=>'<td>'+c+'</td>').join()
      .replace(/,,/g,'</tr><tr>').replace(/,/g,'')
      G.innerHTML='<tr>'+t+'</tr>'
      if (sp<s.length)
        setTimeout(A, 300);  
    })()
  },100)
}

#D { position: relative }
#D input { position: absolute; width: 300px; top:2px; left:2px; border:0 none }
#D select { position: relative; width: 400px; height:1.8em; top:0; left:0; }
textarea{ width: 600px; height: 40px }
td{ width: 1.5em; text-align:right }

Puzzles (select or edit)
<div id=D>
<select id=PZ onchange="B.value=PZ.value,show()">
<option>[5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12]</option>
<option>[2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4]</option>
<option>[5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7]</option>
<option>[11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13]</option>
<option>[5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15]</option>
</select>
<button onclick="solve()">Solve</button>
<input id=B>
</div>
<textarea id=S></textarea>
<table id=G></table>

Conjunto de testes No console Firefox / FireBug

T=~new Date
;[[5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12]
,[2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4]
,[5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7]
,[11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13]
,[5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15]]
.forEach(t=>console.log(t+'',F(t)))
console.log('Time ms ',T-=~new Date)

Saída

"5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12" "D D D L U L D L U R R U U L D D L U U"
"2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4" "D R U L U L L U R D L D R D L U R U L D R D L U R U L U R R R D L L U R D R U L L D L D R U U L D R U R D L U L D D R R U L U L D R U L"
"5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7" "R U U L D D R U L D D R U U L L D D R U L D L U U R R D L U R R D L L U L D D R U U L D D R U U U R R D L L U R R D L L L U R D D L U R D R U U L L D R D L U U"
"11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13" "D L D R U L D D R U L L D L U R R D L U R U R D L U R U L L D R D L L D R U U L D R D L U R U U L D R R U L D R R U L L D L D R U U L D R R D L L U U R D R U L L"
"5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15" "D D R U L L L D R U R D L U U R R D L U L U R D D L U U L D D D R U U L D D R U U U R D R U L D D L U U R D R U L D L L D R U L U R D L D R R U L L U R D D L U U"
"Time ms " 62234

Comecei a trabalhar nesse problema e queria contribuir com meu código até o momento. Como afirma Gareth, o problema é comparável ao quebra-cabeça de 8 blocos e, portanto, o código é baseado na solução magnífica de Keith Randall e, portanto, em Python. Esta solução pode resolver todos os 5 casos de teste com uma soma total de menos de 400 movimentos e outros quebra-cabeças também. Ele contém uma solução otimizada e uma força bruta. O código já está um pouco inchado. A saída é abreviada como "llururd .." Espero que seja útil. http://www.penschuck.org/joomla/tmp/15Tile.txt (explicação) http://www.penschuck.org/joomla/tmp/tile15.txt (código python)

# Author: Heiko Penschuck
# www.penschuck.org
# (C) 2012

# import os;os.chdir('work')
# os.getcwd()

# def execfile(file, globals=globals(), locals=locals()):
#   with open(file, "r") as fh: exec(fh.read()+"\n", globals, locals)
# 
#
# execfile("tile15.py");
#
## run these
# solve_brute();
# solve();



# some boards to play with
board2=(15,14,7,3,13,10,2,9,11,12,4,6,5,0,1,8);
# best: 76(52)  
#    72(56) 
#   68(51)      uurddlurrulldrrdllluuruldrddlururulddruurdllldrurddlurdruuldrdluurdd

board3=(13, 8, 9, 4, 15, 11, 5, 3, 14, 6, 12, 7, 1, 10, 2, 0)
# best: 106(77) 
#best: 90(64)   ullldruuldrrdrlluurulldrrdldluruulddrulurrdrddlluuurdldrrulddrulldrurullldrdluurrrddllurdr

board4=(4, 8, 12, 1, 13, 7, 3, 11, 9, 15, 6, 14, 5, 2, 10, 0) ;# best  100(74)

board5=(15,2,3,4,5,6,7,8,9,10,11,12,13,1,14,0); # best 44(32)
board6=( 1, 2,  3,  4, 6, 11,  0, 12, 8, 14,  9, 13, 5, 10,  7, 15);

# testcases
board7=(5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12); #   15 (7)
board8=(2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4); #  124 (94)
board9=(5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7) ; #  72 (56)
board10=(11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13) ;# 71 (57)
board11=(5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15) ;# 99 (73)

board12=(1,2,3,4,5,6,7,8,9,10,11,12,13,0,14,15); #pretty simple board
board13=(4, 10, 5, 12, 11, 7, 15, 2, 13, 1, 14, 8, 6, 3, 9, 0)

board=board3 ; # used by solve()
bboard=list(board) ;# used by solve_brute()

# init 
clean=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0)
i=0;
solution={};
invsolution={};
E={board:0}


# derived from Keith Randall 8-tile solution
# a: a board, d: offset to move from i: index in board
def Y(a,d,i):
 b=list(a); # b is now an indexable board
 b[i],b[i+d]=b[i+d],0; # make a move (up down left right)
 b=tuple(b); # now back to searchable
 if b not in E:E[b]=a;# store new board in E

def Calc():
 ii=0;
 # memory error when x is 21
 for x in ' '*14:
  if ii>10:
   print(ii);
  ii+=1
  for a in E.copy():
   # for all boards, make possible moves (up,left,right,down) and store the new boards
   i=list(a).index(0)
   if i>3:Y(a,-4,i)
   if i%4:Y(a,-1,i)
   if i%4 <3:Y(a,1,i)
   if i<12:Y(a,4,i)

def weigh(a,goal):
    factor=[26,8,4,6, 8,8,4,4, 4,4,1,1, 3,2,1,0]
    weight=0;
    for element in a:
        i=list(a).index(element);
        ix,iy=divmod(i,4); # ist
        if element == 0:
            # special for gap
            weight=weight+ix;
            #weight+=(ix+iy)
            continue;
        i=list(a).index(element);
        ix,iy=divmod(i,4); # ist
        j=list(goal).index(element);
        sx,sy=divmod(j,4); # soll
        #k=list(a).index(0); # gap
        #kx,ky=divmod(k,4)
        # try solving from topleft to bottom right (because clean board has gap at bottomright)
        tmp= abs(sx-ix)*abs(sx-ix)*factor[j]+ abs(sy-iy)*abs(sy-iy)*factor[j]
        #tmp += ((sx!=ix )& (sy!=iy)) *(4-sx)*(4-sy)*4
        weight+=tmp
        #(10-sx-sy-sy)
        # 8*abs(sx-ix) + (16-j)*(sx!=ix)
        #print('%2d   %2d_%2d (%2d_%2d)=> %d'%(element,i,j,(sx-ix),(sy-iy),weight))
    return weight

# read numbers seperated by a whitespace
def readboard():
    global E,D,board,clean,i
    reset()
    g=[]
    for x in' '*4:g+=map(int,input().split())
    board=tuple(g)

# read 'a' till 'o'
def readasciiboard():
    global E,D,board,clean,i
    trans={"0":0,"a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9,"j":10,"k":11,"l":12,"m":13,"n":14,"o":15}
    reset()
    g=[]
    vec=tuple(input().split());
    for x in vec: g.append(trans[x])
    board=tuple(g)

def printasciiboard(a):
    trans={"0":0,"a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9,"j":10,"k":11,"l":12,"m":13,"n":14,"o":15}
    itrans={}
    for x in trans: itrans[trans[x]]=x
    g=[]
    for x in a: g.append(itrans[x])
    for i in(0,4,8,12): print('%s %s %s %s'%tuple(g[i:i+4]))

# find the board with the smallest weight
def minimum():
    global minn,E,clean
    minn=1111111;# start with a huge number
    qq=board
    for q in E:
        if weigh(q,clean) < minn: 
            minn=weigh(q,clean)
            qq=q
    return qq

# run this and printsolution()
# (you might have to reverse the order of the printed solution)
def solve():
    global start,board,E,clean,minn,solution
    start=board;
    solution={};
    E={ board:0 }
    for x in range(0,11):
        Calc(); # walks all possible moves starting from board to a depth of 10~20 moves
        if clean in E:
            print('Solution found')
            q=clean;
            tmp=[];
            while q:
                tmp.append(q)
                q=E[q]
            for x in reversed(tmp):
                solution[len(solution)]=x;
            printsolution();
            return
        q=minimum();  # calculates the "weight" for all Calc()-ed boards and returns the minimum
        #print("Len %3d"%len(E))
        print("weight %d"%minn)
#       stitch solution
        newboard=q;
        tmp=[];
        while q:
            tmp.append(q)
            q=E[q]
        for x in reversed(tmp):
            solution[len(solution)]=x;
        board=newboard;
        E={board:0}; #reset the Calc()-ed boards
    print("No Solution")


# collects and prints the moves of the solution
# from clean board to given board
# (you have to reverse the order)
def printsolution():
    global invsolution,solution,moves,clean,start
    moves=""
    g=start; # start from board to clean
    y=g
    #invsolution[clean]=0;
    for x in solution:
        # uncomment this if you want to see each board of the solution
        #print(g);
        g=solution[x];
        #sys.stdout.write(transition(y,g))
        if (transition(g,y)=="E"): continue
        moves+=transition(g,y)
        # or as squares
        #print('%10s %d %s'%("step",len(moves),transition(g,y)));
        #print(" %s -- %s "%(y,g))
        #for i in(0,4,8,12): print('%2d %2d %2d %2d'%g[i:i+4])
        y=g         
    llen=len(moves)
    print(" moves%3d "%llen)
    print(moves)
    # processing moves. funny, but occysionally ud,du,lr or rl appears due to the stitching
    while 'lr' in moves:
        a,b,c=moves.partition('lr')
        moves=a+c
        llen-=2
    while 'rl' in moves:
        a,b,c=moves.partition('rl')
        moves=a+c
        llen-=2
    while 'ud' in moves:
        a,b,c=moves.partition('ud')
        moves=a+c
        llen-=2
    while 'du' in moves:
        a,b,c=moves.partition('du')
        moves=a+c
        llen-=2
    # processing moves. concatenating lll to 3l
    while 'lll' in moves:
        a,b,c=moves.partition('lll')
        moves=a+' 3l '+c
        llen-=2
    while 'rrr' in moves:
        a,b,c=moves.partition('rrr')
        moves=a+' 3r '+c
        llen-=2
    while 'uuu' in moves:
        a,b,c=moves.partition('uuu')
        moves=a+' 3u '+c
        llen-=2
    while 'ddd' in moves:
        a,b,c=moves.partition('ddd')
        moves=a+' 3d '+c
        llen-=2

    while 'll' in moves:
        a,b,c=moves.partition('ll')
        moves=a+' 2l '+c
        llen-=1
    while 'rr' in moves:
        a,b,c=moves.partition('rr')
        moves=a+' 2r '+c
        llen-=1
    while 'uu' in moves:
        a,b,c=moves.partition('uu')
        moves=a+' 2u '+c
        llen-=1
    while 'dd' in moves:
        a,b,c=moves.partition('dd')
        moves=a+' 2d '+c
        llen-=1
    print(" processed:%3d "%llen)
    print(moves)

    return

def transition(a,b):
    # calculate the move (ie up,down,left,right)
    # between 2 boards (distance of 1 move and a weight of 1 only)
    i=list(a).index(0);
    j=list(b).index(0);
    if (j==i+1): return "l"
    if (j==i-1): return "r"
    if (j==i-4): return "d"
    if (j==i+4): return "u"
    #print("transition not possible")
    return "E"


###################################################

# below this line are functions for the brute force solution only
# added for comparision
#
# its using a global variable bboard and works destructively on it

def solve_brute():
    global bboard,board;
    bboard=list(board); # working copy
    move(1,0);move(2,1);
    move(3,14); # <== additional move, move 3 out of way
    move(4,2);move(3,6);
    gap_down();gap_down();gap_right();gap_right();gap_up();gap_up();gap_up();gap_left();gap_down();
    #first line solved
    print("first line");printbboard();
    move(5,4);move(6,5);move(7,14);move(8,6);move(7,10);
    gap_down();gap_down();gap_right();gap_right();gap_up();gap_up();gap_left();gap_down();
    #second line solved (upper half)
    print("2nd line");printbboard();
    move(9,15);move(13,8);move(9,9)
    gap_down();gap_left();gap_left();gap_up();gap_right();
    print("left border");printbboard();
    #left border solved
    move(10,15);move(14,9);move(10,10);
    gap_down();movegap(1+3*4);gap_up();gap_right();
    print("left half");printbboard();
    #left half solved

    #rotating last 4 tiles 5 times
    for x in ' '*5:
        gap_right();gap_down(); # gap is now on 15
        if (bboard==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]):
            print("solution found");printbboard();          
            return;
        gap_left();gap_up();
    print("No solution found");
    printbboard();
    return

def printbboard():
    global bboard
    for i in(0,4,8,12): print('%2d %2d %2d %2d'%tuple(bboard[i:i+4]))

def gap_up():
    global bboard
    i=bboard.index(0);
    if (i<4):
        print("Err up()")
        return
    bboard[i],bboard[i-4] = bboard[i-4] , 0 ;

def gap_down():
    global bboard
    i=bboard.index(0);
    if (i>11):
        print("Err down()")
        return
    bboard[i],bboard[i+4] = bboard[i+4] , 0 ;

def gap_left():
    global bboard
    i=bboard.index(0);
    if (i%4<1):
        print("Err left()")
        return  
    bboard[i],bboard[i-1]= bboard[i-1] , 0 ;

def gap_right():
    global bboard
    i=bboard.index(0);
    if (i%4>2):
        print("Err right()")
        return
    bboard[i],bboard[i+1] = bboard[i+1] , 0 ;

def movegap(d): 
    global bboard;
    # d: destination location (0-15)
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    dy,dx=divmod(d,4);
    # moving the gap
    while (ky>dy): 
        gap_up();ky-=1;
    while (ky<dy):
        gap_down();ky+=1;
    while (kx>dx):
        gap_left();kx-=1;
    while (kx<dx):
        gap_right();kx+=1;

def move(s,d):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    dy,dx=divmod(d,4);
    #moving a number
    while (ix<dx):
        move1right(s);
        print("1right ");
        ix+=1;
    while (ix>dx):
        move1left(s);
        ix-=1;
        print("1left ");
    while(iy<dy):
        move1down(s);
        print("1down ");
        iy+=1;
    while(iy>dy):
        move1up(s);
        print("1up");
        iy-=1;

def move1up(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);  
    if (ky<iy):
        # above: move 1 above, then leftorright, then 1 down
        movegap(kx+4*(iy-1))
        movegap(ix+4*(iy-1))
        movegap(ix+4*iy)
        return; # fin
    if (ky==iy):
        # if equal, then first try 1 down
        # (not nescessary if gap is right of s)
        if (kx<ix):
            if (ky<=2):
                movegap(kx+4*(iy+1))
                movegap(ix+1+4*(iy+1)); # 1right 1down of s
                movegap(ix+1+4*(iy-1)); # 1right 1up of s
                movegap(ix+4*(iy-1));# right over s
                gap_down(); # fin
                return;
            # bottom border, must go up first
            movegap(kx+4*(iy-1));
            movegap(ix+4*(iy-1));
            gap_down();
            return; # fin
        else:
            movegap(ix+1+4*iy); # move 1 right of s
            gap_up()
            gap_left()
            gap_down();
            return; # fin
    movegap(ix+1+4*ky); # move 1 right of s
    movegap(ix+1+4*(iy+1)); # move 1 right and 1 down of s
    gap_up();
    gap_up();
    gap_left();
    gap_down();

def move1left(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);  
    if (ky<iy):
        # if above gap move 1 over s
        if (kx<ix):
            movegap(kx+4*iy);
            movegap(ix+4*iy);
            return;# fin
        if (kx==ix):
            #gap over s
            if (ix<3):
                # try to move under s and then left
                if (iy<3):
                    movegap(ix+1+4*ky)
                    movegap(ix+1+4*(iy+1))
                    movegap(ix-1+4*(iy+1))
                    movegap(ix-1+4*iy)
                    movegap(ix+4*iy)
                    return; #fin
            # have to move left         
            movegap(kx-1+4*ky)  
            movegap(ix-1+4*iy)
            movegap(ix+4*iy)
            return;# fin
        # move 1 right of s
        if (iy==3):
            # cant go under, have to go left over
            movegap(kx+4*(iy-1))
            movegap(ix-1+4*(iy-1))
            movegap(ix-1+4*iy)
            movegap(ix+4*iy);
            return; #fin
        movegap(ix+1+4*(iy-1))
        gap_down();gap_down();gap_left();gap_left();gap_up();gap_right();
        return; #fin
    if (ky==iy):
        if (kx<ix):
            movegap(ix-1+4*iy)
            gap_right();
            return; # fin
        if (ky<3):
            gap_down();
            ky+=1;
        else:
            #have to move up
            movegap(ix+4*(iy-1))
            movegap(ix-1+4*(iy-1))
            movegap(ix-1+4*iy)
            gap_right();
            return; #fin
    # gap below s
    movegap(ix+4*(iy+1));
    gap_left();gap_up();gap_right();


def move1right(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);  
    if (ky<iy):
        if (kx==ix):
            movegap(kx+1+4*ky)
            movegap(kx+1+4*iy)
            movegap(ix+4*iy);
            return; #fin
        movegap(kx+4*iy)
        if (kx>ix):
            movegap(ix+4*iy);
            return; #fin
        movegap(kx+4*(iy+1))
        movegap(ix+1+4*(iy+1))
        movegap(ix+1+4*iy);
        movegap(ix+4*iy);
        return; #fin
    if (ky==iy):
        if (kx<ix):
            if (ky>2):
                # bottom row, left of s, have to move 1 up
                gap_up()
                # move 1 right 1 up of s
                movegap(ix+1+4*(ky-1));
                gap_down()
                gap_left()
                return; # fin
            # first 1 down
            movegap(kx+4*(ky+1))
            # to the right of s
            movegap(ix+1+4*(ky+1))
            gap_up()
            gap_left()
            return; # fin
        # already 1 right of s
        movegap(ix+4*iy);
        return; #fin
    # move gap 1 right and 1 down of s
    movegap(kx+4*(iy+1))
    movegap(ix+1+4*(iy+1))
    gap_up();
    gap_left();

def move1down(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);  
    if (ky<iy):
        # gap is over s, move it below
        if (kx==ix):
            if (ix>2):
                # right border, have to move 1 to the left
                movegap(kx+4*(iy-1))
                movegap(kx-1+4*(iy-1))
                movegap(kx-1+4*(iy+1))
                gap_up();
                return; #fin
            # move right of s
            movegap(kx+4*(iy-1))
            movegap(kx+1+4*(iy-1))
            movegap(kx+1+4*(iy+1))
            movegap(kx+4*(iy+1))
            gap_up(); #fin
        movegap(kx+4*(iy+1))
        movegap(ix+4*(iy+1))
        gap_up(); #fin
    if (ky==iy):
        gap_down();
        ky+=1;
    # gap is below s, move 1 under s
    movegap(ix+4*(iy+1))
    gap_up();
    #fin