Le 15 Puzzle est un puzzle célèbre impliquant le glissement de 15 tuiles sur une grille 4x4. Partant d'une configuration aléatoire, l'objectif est de disposer les tuiles dans le bon ordre. Voici un exemple d'un puzzle résolu 15:

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

Chaque mouvement du puzzle est de la forme Haut / Bas / Gauche / Droite. Le mouvement "Down" consiste à faire glisser la tuile qui se trouve au-dessus de la case vide vers le bas. Le mouvement "Droite" consiste à faire glisser une tuile vers la droite, dans la case vide. Voici à quoi ressemble le plateau après les mouvements vers le bas et vers la droite.

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

Le but de ce défi est d'écrire un programme qui peut produire la série de mouvements nécessaires pour résoudre le 15 Puzzle. Le gagnant est le programme qui résout les cinq cas de test (ci-dessous) en un minimum de mouvements. La solution générée n'a pas besoin d'être une solution parfaite, elle doit simplement être meilleure que les concurrents. Pour chaque cas de test individuel, le programme ne devrait pas prendre plus de dix secondes sur une machine raisonnable.

Votre programme doit être capable de résoudre n'importe quel casse-tête qui est résoluble, j'utilise simplement ces cinq cas de test comme pointage.

Votre programme recevra le puzzle 15 non résolu en entrée au format d'un tableau 2D. Le tableau 2D peut être formaté en fonction de la langue utilisée ou modifié si la langue ne possède pas de tableaux 2D. Le premier élément du premier sous-tableau sera le numéro en haut à gauche et le dernier élément du premier sous-tableau sera le numéro en haut à droite. A 0sera l'espace vide.

En sortie, votre programme doit imprimer une liste de mouvements dans l'ordre dans lequel ils doivent être effectués. Chaque étape doit être numérotée afin d'augmenter l'utilisabilité des résultats.

EDIT: Sur la base des commentaires, je permettrai que la sortie soit sous la forme Down / Up / etc ou sous la forme des coordonnées de la pièce à déplacer. Comme ce n'est pas du golf de code, la partie la plus importante est de résoudre le puzzle.

Certaines autres règles générales n'impliquent pas l'utilisation d'une source externe, etc.

Cas de test 1

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

Exemple de sortie:

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

Cas de test 2

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

Cas de test 3

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

Cas de test 4

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

Cas de test 5

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

PyPy, 195 mouvements, ~ 12 secondes de calcul

Calcule des solutions optimales en utilisant IDA * avec une heuristique de «distance de marche» augmentée de conflits linéaires. Voici les solutions optimales:

 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

Et le code:

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)

JavaScript (ES6) total des étapes 329 pour les 5 cas de test en ~ 1 min

Modifier Même stratégie, cibles différentes, meilleure solution. Ralentissez ...

C'est plus ou moins comment je le résous à la main: utiliser des cibles intermédiaires Après chaque cible, les tuiles relatives ne sont plus déplacées Chaque cible intermédiaire est atteinte à l'aide d'une fonction BSF paramétrique. Les 2 paramètres sont la condition de boucle L (répéter si vrai) et la condition de sélection S (sélectionner quelle tuile peut être déplacée). Les marches:

1. Placer 1 haut / gauche
2. Place 2
3. Place 5
4. Place 3,4 - rangée du haut ok
5. Place 9,13 - colonne de gauche ok
6. Tout le reste

Note latérale Je ne vérifie pas la position des tuiles 14 et 15. Les énigmes insolubles comme [11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]auront 14 et 15 échangées.

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)
)

Extrait ouvert pour tester ou jouer (Firefox uniquement)

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>

Suite de tests dans la 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)

Sortie

"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

J'ai commencé à travailler sur ce problème et je voulais contribuer avec mon code jusqu'à présent. Comme indiqué par Gareth, le problème est comparable au casse-tête à 8 carreaux et le code est donc basé sur la magnifique solution de Keith Randall et donc en Python. Cette solution peut résoudre les 5 cas de test avec une somme totale de moins de 400 mouvements, ainsi que d'autres puzzles. Il contient une solution optimisée et une force brute. Le code est un peu gonflé maintenant. La sortie est abrégée comme "llururd .." J'espère que c'est utile. http://www.penschuck.org/joomla/tmp/15Tile.txt (explication) http://www.penschuck.org/joomla/tmp/tile15.txt (code 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