Solve the 15 Puzzle (the tile-sliding puzzle)
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.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 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:
- Place 1 top/left
- Place 2
- Place 5
- Place 3,4 - top row ok
- Place 9,13 - left column ok
- 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
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