# Solve the 15 Puzzle (the tile-sliding puzzle)

The 15 Puzzle is a famous puzzle involving sliding 15 tiles around on a 4x4 grid. Starting from a random configuration, the goal is to arrange the tiles in the correct order. Here is an example of a solved 15 Puzzle:

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


Each move on the puzzle is of the form Up/Down/Left/Right. The move "Down" consists of sliding the tile that is above the empty spot downward. The move "Right" consists of sliding a tile to the right, into the empty spot. Here is how the board looks after the moves Down and Right.

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


The goal of this challenge is to write a program that can output the series of moves needed to solve the 15 Puzzle. The winner is the program who solves the five test cases (below) in the fewest total moves. The generated solution does not need to be a perfect solution, it merely has to be better than the competitors. For each individual test case, the program should not take more than ten seconds on a reasonable machine.

Your program must be able to solve any puzzle that is solvable, I'm just using these five test cases as the scoring.

Your program will receive the unsolved 15 Puzzle as input in the format of a 2D array. The 2D array can be formatted according to the language used, or changed if the language does not have 2D arrays. The first element of the first sub-array will be the number in the upper left, and the last element of the first sub-array will be the number in the upper right. A 0 will be the empty space.

As output, your program should print a list of moves in the order that they need to be performed. Each step should be numbered in order to increase the usability of the results.

EDIT: Based on comments, I will allow output to be in either the form of Down/Up/etc or in the form of the coordinates of the piece to move. As this is not code golf, the most important part is to solve the puzzle.

Some other general rules involve no using an outside source, etc.

Test Case 1

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


Example Output:

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


Test Case 2

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


Test Case 3

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


Test Case 4

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


Test Case 5

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

• Must the solver be able to solve more than just these 5? – Matt Aug 3 '12 at 17:46
• – Gareth Aug 3 '12 at 17:46
• @Matt It should be able to solve any puzzle that is solvable. I thought that was implied, but I'll make it more explicit. – PhiNotPi Aug 3 '12 at 17:50
• the way i am doing would be more easy to output the moves as single coordinates. like, you move that coordinate to the only legal move (the withe space). Is outputing in this way allowed? – ajax333221 Aug 3 '12 at 20:46
• @ajax333221 I like that style of output more since it is easier to generate from most languages. – FUZxxl Aug 4 '12 at 13:35

# PyPy, 195 moves, ~12 seconds computation

Computes optimal solutions using IDA* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions:

 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


And the 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.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)

• Would it be ok with you if I posted this solution on Rosetta Code and made sure that it was clear that it came from you and this post? I've been working on a Python based 15 puzzle solver for this RC task: rosettacode.org/wiki/15_puzzle_solver but it has been a challenge to get my code to solve a length 52 path in a reasonable length of time. Your solution runs in a few seconds. I was just thinking about doing my own IDA* version but yours already works. My current solver is based on A*. We just need a Python example. Anyway, let me know if it is ok to use this one. – Bobby Durrett Oct 30 '18 at 22:57
• @BobbyDurrett That's more than fine. It's not particularly clear code though. – orlp Oct 31 '18 at 1:32
• Thanks. I think I will keep working on mine for my own education and post it too if I get it working well enough. I thought I might as well put yours up there so there is a Python example. – Bobby Durrett Oct 31 '18 at 14:50

# JavaScript (ES6) total steps 329 for all 5 test cases in ~1min

Edit Same strategy, different targets, better solution. Slower ...

This is more or less how I solve it by hand: using intermediate targets After each target the relative tiles are not moved again Each intermediate target is reached using a parametric BSF function. The 2 params are the loop condition L (repeat while true) and the select condition S (select what tile can be moved). The steps:

1. Place 1 top/left
2. Place 2
3. Place 5
4. Place 3,4 - top row ok
5. Place 9,13 - left column ok
6. All the rest

Side note I don't check the position of tiles 14 and 15. Unsolvable puzzles like [11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13] will have 14 and 15 swapped.

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


Open snippet to test or play (Firefox only)

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>

Test suite In Firefox/FireBug console

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)


Output

"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


I started working on this problem and wanted to contribute with my code so far. As stated by Gareth, the problem is comparable to the 8-tile puzzle and so the code is based on the magnificient solution of Keith Randall and thus in Python. This solution can solve all 5 test cases with a total sum of less than 400 moves, and other puzzles, too. It contains an optimized and a brute force solution. The code is a bit bloated by now. Output is abbrevated like "llururd.." Hope its helpful. http://www.penschuck.org/joomla/tmp/15Tile.txt (explanation) http://www.penschuck.org/joomla/tmp/tile15.txt (python code)

# 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
global E,D,board,clean,i
reset()
g=[]
for x in' '*4:g+=map(int,input().split())
board=tuple(g)

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