(Fortran) ! See link.
(Python) # alst(), swap(), moves() useful for other sliding puzzle problems
def swap(p, z, nz):
lp = list(p)
lp[z], lp[nz] = lp[nz], "-"
return "".join(lp)
def moves(p, shape): # moves for n x m sliding puzzle
nxt, (n, m), z = [], shape, p.find("-") # z: blank location
if z > n - 1: nxt.append(swap(p, z, z-n)) # blank up
if z < n*m-n: nxt.append(swap(p, z, z+n)) # blank down
if z%n != 0: nxt.append(swap(p, z, z-1)) # blank left
if z%n != n-1: nxt.append(swap(p, z, z+1)) # blank right
return nxt
def alst(start, shape, v=False, maxd=float('inf')):
alst, d, expanded, frontier = [], 0, set(), {start}
alst.append(len(frontier))
if v: print(len(frontier), end=", ")
while len(frontier) > 0 and d < maxd:
reach1 = set(m for p in frontier for m in moves(p, shape) if m not in expanded)
expanded |= frontier # expanded = frontier # ALTERNATE using less memory
if len(reach1):
alst.append(len(reach1))
if v: print(len(reach1), end=", ")
frontier = reach1
d += 1
return alst
