15 Puzzle adalah teka-teki terkenal yang melibatkan 15 ubin bergeser di sekitar kotak 4x4. Mulai dari konfigurasi acak, tujuannya adalah untuk mengatur ubin dalam urutan yang benar. Berikut adalah contoh dari 15 Puzzle yang dipecahkan:

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

Setiap gerakan pada puzzle adalah dalam bentuk Atas / Bawah / Kiri / Kanan. Langkah "Bawah" terdiri dari menggeser ubin yang ada di atas tempat kosong ke bawah. Langkah "Kanan" terdiri dari menggeser ubin ke kanan, ke tempat kosong. Berikut adalah tampilan papan setelah gerakan ke Bawah dan Kanan.

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

Tujuan dari tantangan ini adalah untuk menulis sebuah program yang dapat menghasilkan serangkaian langkah yang diperlukan untuk menyelesaikan 15 Puzzle. Pemenangnya adalah program yang menyelesaikan lima kasus uji (di bawah) dalam total gerakan paling sedikit. Solusi yang dihasilkan tidak perlu menjadi solusi yang sempurna, itu hanya harus lebih baik dari para pesaing. Untuk setiap kasus uji individual, program tidak boleh memakan waktu lebih dari sepuluh detik pada mesin yang masuk akal.

Program Anda harus dapat memecahkan setiap teka-teki yang dapat dipecahkan, saya hanya menggunakan lima test case ini sebagai skor.

Program Anda akan menerima 15 Puzzle yang belum terpecahkan sebagai input dalam format array 2D. Array 2D dapat diformat sesuai dengan bahasa yang digunakan, atau diubah jika bahasa tidak memiliki array 2D. Elemen pertama dari sub-array pertama adalah angka di kiri atas, dan elemen terakhir dari sub-array pertama adalah angka di kanan atas. A 0akan menjadi ruang kosong.

Sebagai hasil, program Anda harus mencetak daftar gerakan dalam urutan yang harus dilakukan. Setiap langkah harus diberi nomor untuk meningkatkan kegunaan hasil.

EDIT: Berdasarkan komentar, saya akan mengizinkan output dalam bentuk Down / Up / etc atau dalam bentuk koordinat potongan untuk bergerak. Karena ini bukan kode golf, bagian terpenting adalah memecahkan teka-teki.

Beberapa aturan umum lainnya tidak boleh menggunakan sumber luar, dll.

Test Case 1

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

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

PyPy, 195 bergerak, ~ perhitungan 12 detik

Menghitung solusi optimal menggunakan IDA * dengan heuristik 'berjalan kaki' ditambah dengan konflik linear. Berikut adalah solusi optimal:

 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

Dan kodenya:

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 langkah 329 untuk semua 5 kasus uji dalam ~ 1 menit

Edit Strategi yang sama, target yang berbeda, solusi yang lebih baik. Lebih lambat ...

Ini lebih atau kurang bagaimana saya menyelesaikannya dengan tangan: menggunakan target menengah Setelah setiap target ubin relatif tidak dipindahkan lagi Setiap target menengah tercapai menggunakan fungsi BSF parametrik. 2 params adalah kondisi loop L (repeat while true) dan kondisi select S (pilih tile apa yang bisa dipindahkan). Langkah langkah:

1. Tempatkan 1 atas / kiri
2. Tempat 2
3. Tempat 5
4. Tempatkan 3,4 - baris paling atas ok
5. Tempat 9,13 - kolom kiri ok
6. Sisanya

Catatan sisi Saya tidak memeriksa posisi ubin 14 dan 15. Teka-teki yang tidak dapat dipecahkan seperti [11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]memiliki 14 dan 15 ditukar.

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

Buka cuplikan untuk diuji atau mainkan (khusus 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>

Test suite Di konsol 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)

Keluaran

"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

Saya mulai mengerjakan masalah ini dan ingin berkontribusi dengan kode saya sejauh ini. Seperti yang dinyatakan oleh Gareth, masalahnya adalah sebanding dengan puzzle 8-ubin dan kode ini didasarkan pada solusi Keith Randall yang lebih baik dan dengan demikian dalam Python. Solusi ini dapat menyelesaikan semua 5 kasus uji dengan jumlah total kurang dari 400 gerakan, dan juga teka-teki lainnya. Ini berisi solusi yang dioptimalkan dan brute force. Kode sudah agak membengkak sekarang. Output disingkat seperti "llururd .." Semoga bermanfaat. http://www.penschuck.org/joomla/tmp/15Tile.txt (penjelasan) http://www.penschuck.org/joomla/tmp/tile15.txt (kode 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