/############# / positions
/#12.3.4.5.67#
/###8#a#c#e###
/  #9#b#d#f#
/  #########

/#############
/#12.3.4.5.67#
/###8#c#g#k###  8 12 16 20
/  #9#d#h#l#    9 13 17 21
/  #a#e#i#m#   10 14 18 22
/  #b#f#j#n#   11 15 19 23
/  #########

/ pieces: empty=0 a=1 b=2 c=3 d=4 (base 5)

pr:1000003          / prime
s:{(,x)!0N}'!pr     / hashtable: positions -> score
H:5/
g:{(s@pr!h)@h:H@x}  / get
p:{s[pr!h;h:H@x]:y} / put

search:{r:search[x|a]'i:&~~a:(~x)*adj y;a|/(~~r)*r+a@i}
nexts:{
 i:&~~x
 isown:~^(M2@x@i)?'i
 fc:(1+(!5)*1&/'(!5)=(x@M2)^'0)@x@i
 m:2!&'M1(isown*(1<fc)*i>7)+fc*i<8
 n:((0,3(10*)\1)x@i)*m*search[x]'i
 boards:,'p@[x;;:]'0,'x@*'p:,/i,/:'&'~~n
 boards,'(,/n)^0}
f:{p[init;0];{?{p[*x;x[1]&x[1]^g@*x];*x}',/(0,'g'x)+/:'nexts'x}/,init;g@fin}

init:(8#0),2,1,3,4,2,3,4,1
init:(8#0),4,4,1,3,3,2,1,2
fin: (8#0),1,1,2,2,3,3,4,4
adj:(()     / dist,pos
     ,1 2
     (1 1; 2 8; 2 3)
     (2 2; 2 8; 2 10; 2 4)
     (2 3; 2 10; 2 12; 2 5)
     (2 4; 2 12; 2 14; 2 6)
     (2 5; 2 14; 1 7)
     ,1 6
     (2 2; 2 3; 1 9)
     ,1 8
     (2 3; 2 4; 1 11)
     ,1 10
     (2 4; 2 5; 1 13)
     ,1 12
     (2 5; 2 6; 1 15)
     ,1 14)
adj:((16#0){@[x;*|y;:;*y]}/)'adj
M1:(0 8 8;16;8 2 6;10 2 4;12 2 2;14 2)
M2:0,4 2#8+!8
f[]

init:(8#0),2,4,4,1,3,3,2,4,2,2,1,3,4,1,3,1
init:(8#0),4,4,4,4,1,3,2,3,3,2,1,2,1,1,3,2
fin: (8#0),1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4
adj:(()     / dist,pos
     ,1 2
     (1 1; 2  8; 2 3)
     (2 2; 2  8; 2 12; 2 4)
     (2 3; 2 12; 2 16; 2 5)
     (2 4; 2 16; 2 20; 2 6)
     (2 5; 2 20; 1 7)
     ,1 6
     (2 2; 2 3; 1 9)
     (1 8; 1 10)
     (1 9; 1 11)
     ,1 10
     (2 3; 2 4; 1 13)
     (1 12; 1 14)
     (1 13; 1 15)
     ,1 14
     (2 4; 2 5; 1 17)
     (1 16; 1 18)
     (1 17; 1 19)
     ,1 18
     (2 5; 2 6; 1 21)
     (1 20; 1 22)
     (1 21; 1 23)
     ,1 22)
adj:((24#0){@[x;*|y;:;*y]}/)'adj
M1:(0 8 16;24;8 4 12;12 4 8;16 4 4;20 4)
M2:0,4 4#8+!16
f[]