15 puzzle solver: Difference between revisions

From Rosetta Code
Content added Content deleted
m (minor typo)
No edit summary
Line 1: Line 1:
{{task|Games}}
{{task|Games}}
Your task is to write a program that finds a solution in the fewest moves possible to a random [[wp:15_puzzle|Fifteen Puzzle Game]].<br />
Your task is to write a program that finds a solution in the fewest single moves (no multimoves) possible to a random [[wp:15_puzzle|Fifteen Puzzle Game]].<br />
For this task you will be using the following puzzle:<br />
For this task you will be using the following puzzle:<br />
<pre>15 14 1 6
<pre>15 14 1 6
Line 14: Line 14:
</pre>
</pre>
The output must show the moves' directions, like so: left, left, left, down, right... and so on.<br />
The output must show the moves' directions, like so: left, left, left, down, right... and so on.<br />
There are 2 solutions with 52 moves:<br>
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd<br>
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd<br>


see: [http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution Pretty Print of Optimal Soltion]
see: [http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution Pretty Print of Optimal Solution]


;Extra credit.
;Extra credit.
Line 34: Line 37:




;Related Task:
;Related Tasks:
* [[15_Puzzle_Game|15 puzzle game]]
* [[15_Puzzle_Game|15 puzzle game]]
* [[15_puzzle_solver/Multimove|15 puzzle solver allowing multimoves]]
<br><br>
<br><br>


=={{header|C++}}==
=={{header|C++}}==
{{incorrect|C++|The task calls for a solution in the fewest moves which is 31 not 52}}
===Staying Functional (as possible in C++)===
===Staying Functional (as possible in C++)===
====The Solver====
====The Solver====
Line 230: Line 233:


=={{header|F_Sharp|F#}}==
=={{header|F_Sharp|F#}}==
{{incorrect|F#|The task calls for a solution in the fewest moves which is 31 not 52}}
<lang fsharp>
<lang fsharp>
// A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017
// A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017
Line 295: Line 297:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
</pre>
</pre>

=={{header|Phix}}==
<lang Phix>--
-- demo\rosetta\Solve15puzzle.exw
--
constant STM = 0 -- single-tile metrics.
constant MTM = 0 -- multi-tile metrics.
if STM and MTM then ?9/0 end if -- both prohibited
-- 0 0 -- fastest, but non-optimal
-- 1 0 -- optimal in STM
-- 0 1 -- optimal in MTM (slowest by far)

--Note: The fast method uses an inadmissible heuristic - see "not STM" in iddfs().
-- It explores mtm-style using the higher stm heuristic and may therefore
-- fail badly in some cases.

constant SIZE = 4

constant goal = { 1, 2, 3, 4,
5, 6, 7, 8,
9,10,11,12,
13,14,15, 0}

--
-- multi-tile-metric walking distance heuristic lookup (mmwd).
-- ==========================================================
-- Uses patterns of counts of tiles in/from row/col, eg the solved state
-- (ie goal above) could be represented by the following:
-- {{4,0,0,0},
-- {0,4,0,0},
-- {0,0,4,0},
-- {0,0,0,3}}
-- ie row/col 1 contains 4 tiles from col/row 1, etc. In this case
-- both are identical, but you can count row/col or col/row, and then
-- add them together. There are up to 24964 possible patterns. The
-- blank space is not counted. Note that a vertical move cannot change
-- a vertical pattern, ditto horizontal, and basic symmetry means that
-- row/col and col/row patterns will match (at least, that is, if they
-- are calculated sympathetically), halving the setup cost.
-- The data is just the number of moves made before this pattern was
-- first encountered, in a breadth-first search, backwards from the
-- goal state, until all patterns have been enumerated.
-- (The same ideas/vars are now also used for stm metrics when MTM=0)
--
sequence wdkey -- one such 4x4 pattern
constant mmwd = new_dict() -- lookup table, data is walking distance.


--
-- We use two to-do lists: todo is the current list, and everything
-- of walkingdistance+1 ends up on tdnx. Once todo is exhausted, we
-- swap the dictionary-ids, so tdnx automatically becomes empty.
-- Key is an mmwd pattern as above, and data is {distance,space_idx}.
--
integer todo = new_dict()
integer tdnx = new_dict()

--

enum UP = 1, DOWN = -1

procedure explore(integer space_idx, walking_distance, direction)
--
-- Given a space index, explore all the possible moves in direction,
-- setting the distance and extending the tdnx table.
--
integer tile_idx = space_idx+direction
for group=1 to SIZE do
if wdkey[tile_idx][group] then
-- ie: check row tile_idx for tiles belonging to rows 1..4
-- Swap one of those tiles with the space
wdkey[tile_idx][group] -= 1
wdkey[space_idx][group] += 1

if getd_index(wdkey,mmwd)=0 then
-- save the walking distance value
setd(wdkey,walking_distance+1,mmwd)
-- and add to the todo next list:
if getd_index(wdkey,tdnx)!=0 then ?9/0 end if
setd(wdkey,{walking_distance+1,tile_idx},tdnx)
end if

if MTM then
if tile_idx>1 and tile_idx<SIZE then
-- mtm: same direction means same distance:
explore(tile_idx, walking_distance, direction)
end if
end if

-- Revert the swap so we can look at the next candidate.
wdkey[tile_idx][group] += 1
wdkey[space_idx][group] -= 1
end if
end for
end procedure

procedure generate_mmwd()
-- Perform a breadth-first search begining with the solved puzzle state
-- and exploring from there until no more new patterns emerge.
integer walking_distance = 0, space = 4

wdkey = {{4,0,0,0}, -- \
{0,4,0,0}, -- } 4 tiles in correct row positions
{0,0,4,0}, -- /
{0,0,0,3}} -- 3 tiles in correct row position
setd(wdkey,walking_distance,mmwd)
while 1 do
if space<4 then explore(space, walking_distance, UP) end if
if space>1 then explore(space, walking_distance, DOWN) end if
if dict_size(todo)=0 then
if dict_size(tdnx)=0 then exit end if
{todo,tdnx} = {tdnx,todo}
end if
wdkey = getd_partial_key(0,todo)
{walking_distance,space} = getd(wdkey,todo)
deld(wdkey,todo)
end while
end procedure

function walking_distance(sequence puzzle)
sequence rkey = repeat(repeat(0,SIZE),SIZE),
ckey = repeat(repeat(0,SIZE),SIZE)
integer k = 1
for i=1 to SIZE do -- rows
for j=1 to SIZE do -- columns
integer tile = puzzle[k]
if tile!=0 then
integer row = floor((tile-1)/4)+1,
col = mod(tile-1,4)+1
rkey[i][row] += 1
ckey[j][col] += 1
end if
k += 1
end for
end for
if getd_index(rkey,mmwd)=0
or getd_index(ckey,mmwd)=0 then
?9/0 -- sanity check
end if
integer rwd = getd(rkey,mmwd),
cwd = getd(ckey,mmwd)
return rwd+cwd
end function

sequence puzzle
string res = ""
atom t0 = time(),
t1 = time()+1
atom tries = 0

constant ok = {{0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1}, -- left
{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1}, -- up
{1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}, -- down
{1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0}} -- right

function iddfs(integer step, lim, space, prevmv)
if time()>t1 then
printf(1,"working... (depth=%d, tries=%d, time=%3ds)\r",{lim,tries,time()-t0})
t1 = time()+1
end if
tries += 1
integer d = iff(step==lim?0:walking_distance(puzzle))
if d=0 then

return (puzzle==goal)

elsif step+d<=lim then

for mv=1 to 4 do -- l/u/d/r
if prevmv!=(5-mv) -- not l after r or vice versa, ditto u/d
and ok[mv][space] then
integer nspace = space+{-1,-4,+4,+1}[mv]
integer tile = puzzle[nspace]
if puzzle[space]!=0 then ?9/0 end if -- sanity check
puzzle[space] = tile
puzzle[nspace] = 0
if iddfs(step+iff(MTM or not STM?(prevmv!=mv):1),lim,nspace,mv) then
res &= "ludr"[mv]
return true
end if
puzzle[nspace] = tile
puzzle[space] = 0
end if
end for
end if
return false
end function

function pack(string s)
integer n = length(s), n0 = n
for i=1 to 4 do
integer ch = "lrud"[i], k
while 1 do
k = match(repeat(ch,3),s)
if k=0 then exit end if
s[k+1..k+2] = "3"
n -= 2
end while
while 1 do
k = match(repeat(ch,2),s)
if k=0 then exit end if
s[k+1] = '2'
n -= 1
end while
end for
return {n,iff(MTM?sprintf("%d",n):sprintf("%d(%d)",{n,n0})),s}
end function

procedure apply_moves(string moves, integer space)
integer move, ch, nspace
puzzle[space] = 0
for i=1 to length(moves) do
ch = moves[i]
if ch>'3' then
move = find(ch,"ulrd")
end if
-- (hint: "r" -> the 'r' does 1
-- "r2" -> the 'r' does 1, the '2' does 1
-- "r3" -> the 'r' does 1, the '3' does 2!)
for j=1 to 1+(ch='3') do
nspace = space+{-4,-1,+1,4}[move]
puzzle[space] = puzzle[nspace]
space = nspace
puzzle[nspace] = 0
end for
end for
end procedure

function solvable(sequence board)
integer n = length(board)
sequence positions = repeat(0,n)
-- prepare the mapping from each tile to its position
board[find(0,board)] = n
for i=1 to n do
positions[board[i]] = i
end for
-- check whether this is an even or odd state
integer row = floor((positions[16]-1)/4),
col = (positions[16]-1)-row*4
bool even_state = (positions[16]==16) or (mod(row,2)==mod(col,2))
-- count the even cycles
integer even_count = 0
sequence visited = repeat(false,16)
for i=1 to n do
if not visited[i] then
-- a new cycle starts at i. Count its length..
integer cycle_length = 0,
next_tile = i
while not visited[next_tile] do
cycle_length +=1
visited[next_tile] = true
next_tile = positions[next_tile]
end while
even_count += (mod(cycle_length,2)==0)
end if
end for
return even_state == (mod(even_count,2)==0)
end function

procedure main()

puzzle = {15,14, 1, 6,
9,11, 4,12,
0,10, 7, 3,
13, 8, 5, 2}

if not solvable(puzzle) then
?puzzle
printf(1,"puzzle is not solveable\n")
else

generate_mmwd()

sequence original = puzzle
integer space = find(0,puzzle)

for lim=walking_distance(puzzle) to iff(MTM?43:80) do
if iddfs(0, lim, space, '-') then exit end if
end for

{integer n, string ns, string ans} = pack(reverse(res))

printf(1,"\n\noriginal:")
?original
atom t = time()-t0
printf(1,"\n%soptimal solution of %s moves found in %s: %s\n\nresult: ",
{iff(MTM?"mtm-":iff(STM?"stm-":"non-")),ns,elapsed(t),ans})
puzzle = original
apply_moves(ans,space)
?puzzle
end if
end procedure
main()</lang>
{{out}}
<pre>
original:{15,14,1,6,9,11,4,12,0,10,7,3,13,8,5,2}
non-optimal solution of 35(60) moves found in 2.42s: u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru2ldru2rd3lulur3dl2ur2d2
stm-optimal solution of 38(52) moves found in 1 minute and 54s: r3uldlu2ldrurd3lu2lur3dld2ruldlu2rd2lulur2uldr2d2
mtm-optimal solution of 31(60) moves found in 2 hours, 38 minutes and 28s: u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru3rd3l2u2r3dl3dru2r2d2
</pre>

Partial extra credit:
<pre>
{2,1,3,4,5,6,7,8,9,10,11,12,13,14,15,0}
puzzle is not solveable
</pre>
No luck on the other one, a non-optimal 60(98) moves was the best it could manage.

Revision as of 09:58, 24 October 2017

Task
15 puzzle solver
You are encouraged to solve this task according to the task description, using any language you may know.

Your task is to write a program that finds a solution in the fewest single moves (no multimoves) possible to a random Fifteen Puzzle Game.
For this task you will be using the following puzzle:

15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2


Solution:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are 2 solutions with 52 moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd

see: Pretty Print of Optimal Solution

Extra credit.

Solve the following problems: 

 2  1  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

and 

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1


Related Tasks



C++

Staying Functional (as possible in C++)

The Solver

Translation of: FSharp

<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 11th., 2017 const int Nr[]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}; using N = std::tuple<int,int,unsigned long,std::string,int>; void fN(const N,const int); const N fI(const N n){ 

 int           g = (11-std::get<1>(n)-std::get<0>(n)*4)*4;
 unsigned long a = std::get<2>(n)&((unsigned long)15<<g);
 return N (std::get<0>(n)+1,std::get<1>(n),std::get<2>(n)-a+(a<<16),std::get<3>(n)+"d",(Nr[a>>g]<=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);

} const N fG(const N n){ 

 int           g = (19-std::get<1>(n)-std::get<0>(n)*4)*4;
 unsigned long a = std::get<2>(n)&((unsigned long)15<<g);
 return N (std::get<0>(n)-1,std::get<1>(n),std::get<2>(n)-a+(a>>16),std::get<3>(n)+"u",(Nr[a>>g]>=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);

} const N fE(const N n){ 

 int           g = (14-std::get<1>(n)-std::get<0>(n)*4)*4;
 unsigned long a = std::get<2>(n)&((unsigned long)15<<g);
 return N (std::get<0>(n),std::get<1>(n)+1,std::get<2>(n)-a+(a<<4),std::get<3>(n)+"r",(Nc[a>>g]<=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);

} const N fL(const N n){ 

 int           g = (16-std::get<1>(n)-std::get<0>(n)*4)*4;
 unsigned long a = std::get<2>(n)&((unsigned long)15<<g);
 return N (std::get<0>(n),std::get<1>(n)-1,std::get<2>(n)-a+(a>>4),std::get<3>(n)+"l",(Nc[a>>g]>=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);

} void fZ(const N n, const int g){ 

 if (std::get<2>(n)==0x123456789abcdef0){
   int g{};for (char a: std::get<3>(n)) ++g;
   std::cout<<"Solution found with "<<g<<" moves: "<<std::get<3>(n)<<std::endl; exit(0);}
 if (std::get<4>(n) <= g) fN(n,g);

} void fN(const N n, const int g){ 

 const int i{std::get<0>(n)}, e{std::get<1>(n)}, l{std::get<3>(n).back()};
 switch(i){case  0: switch(e){case  0: switch(l){case 'l': fZ(fI(n),g); return;
                                                 case 'u': fZ(fE(n),g); return;
                                                 default : fZ(fE(n),g); fZ(fI(n),g); return;}
                              case  3: switch(l){case 'r': fZ(fI(n),g); return;
                                                 case 'u': fZ(fL(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fI(n),g); return;}
                              default: switch(l){case 'l': fZ(fI(n),g); fZ(fL(n),g); return;
                                                 case 'r': fZ(fI(n),g); fZ(fE(n),g); return;
                                                 case 'u': fZ(fE(n),g); fZ(fL(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); return;}}
           case  3: switch(e){case  0: switch(l){case 'l': fZ(fG(n),g); return;
                                                 case 'd': fZ(fE(n),g); return;
                                                 default : fZ(fE(n),g); fZ(fG(n),g); return;}
                              case  3: switch(l){case 'r': fZ(fG(n),g); return;
                                                 case 'd': fZ(fL(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fG(n),g); return;}
                              default: switch(l){case 'l': fZ(fG(n),g); fZ(fL(n),g); return;
                                                 case 'r': fZ(fG(n),g); fZ(fE(n),g); return;
                                                 case 'd': fZ(fE(n),g); fZ(fL(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fG(n),g); fZ(fE(n),g); return;}}
           default: switch(e){case  0: switch(l){case 'l': fZ(fI(n),g); fZ(fG(n),g); return;
                                                 case 'u': fZ(fE(n),g); fZ(fG(n),g); return;
                                                 case 'd': fZ(fE(n),g); fZ(fI(n),g); return;
                                                 default : fZ(fE(n),g); fZ(fI(n),g); fZ(fG(n),g); return;}
                              case  3: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); return;
                                                 case 'u': fZ(fL(n),g); fZ(fG(n),g); return;
                                                 case 'r': fZ(fI(n),g); fZ(fG(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fI(n),g); fZ(fG(n),g); return;}
                              default: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); fZ(fE(n),g); return;
                                                 case 'l': fZ(fI(n),g); fZ(fL(n),g); fZ(fG(n),g); return;
                                                 case 'r': fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return;
                                                 case 'u': fZ(fE(n),g); fZ(fL(n),g); fZ(fG(n),g); return;
                                                 default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return;}}}

} void Solve(N n){for(int g{};;++g) fN(n,g);} </lang>

The Task

<lang cpp> int main (){ 

 N start(2,0,0xfe169b4c0a73d852,"",0);
 Solve(start);

} </lang>

Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

real    0m2.897s
user    0m2.887s
sys     0m0.008s

Time to get Imperative

see for an analysis of 20 randomly generated 15 puzzles solved with this solver.

The Solver

<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017 class fifteenSolver{ 

 const int Nr[16]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[16]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}, i{1}, g{8}, e{2}, l{4};
 int n{},_n{}, N0[85]{},N1[85]{},N3[85]{},N4[85];
 unsigned long N2[85]{};
 bool fU(){
   if (N2[n]==0x123456789abcdef0) return true; 
   if (N4[n]<=_n) return fN();
   return false;
 }
 bool fZ(const int w){
   int a = n;
   if ((w&i)>0){fI(); if (fU()) return true; n=a;}
   if ((w&g)>0){fG(); if (fU()) return true; n=a;}
   if ((w&e)>0){fE(); if (fU()) return true; n=a;}
   if ((w&l)>0){fL(); return fU();}
   return false;
 }
 bool fN(){
   switch(N0[n]){case  0: switch(N1[n]){case  0: switch(N3[n]){case 'l': return fZ(i);
                                                               case 'u': return fZ(e);
                                                               default : return fZ(i+e);}
                                        case  3: switch(N3[n]){case 'r': return fZ(i);
                                                               case 'u': return fZ(l);
                                                               default : return fZ(i+l);}
                                        default: switch(N3[n]){case 'l': return fZ(i+l);
                                                               case 'r': return fZ(i+e);
                                                               case 'u': return fZ(e+l);
                                                               default : return fZ(i+e+l);}}
                 case  3: switch(N1[n]){case  0: switch(N3[n]){case 'l': return fZ(g);
                                                               case 'd': return fZ(e);
                                                               default : return fZ(e+g);}
                                        case  3: switch(N3[n]){case 'r': return fZ(g);
                                                               case 'd': return fZ(l);
                                                               default : return fZ(g+l);}
                                        default: switch(N3[n]){case 'l': return fZ(g+l);
                                                               case 'r': return fZ(e+g);
                                                               case 'd': return fZ(e+l);
                                                               default : return fZ(g+e+l);}}
                 default: switch(N1[n]){case  0: switch(N3[n]){case 'l': return fZ(i+g);
                                                               case 'u': return fZ(g+e);
                                                               case 'd': return fZ(i+e);
                                                               default : return fZ(i+g+e);}
                                        case  3: switch(N3[n]){case 'd': return fZ(i+l);
                                                               case 'u': return fZ(g+l);
                                                               case 'r': return fZ(i+g);
                                                               default : return fZ(i+g+l);}
                                        default: switch(N3[n]){case 'd': return fZ(i+e+l);
                                                               case 'l': return fZ(i+g+l);
                                                               case 'r': return fZ(i+g+e);
                                                               case 'u': return fZ(g+e+l);
                                                               default : return fZ(i+g+e+l);}}}
 }
 void fI(){
   int           g = (11-N1[n]-N0[n]*4)*4;
   unsigned long a = N2[n]&((unsigned long)15<<g);
   N0[n+1]=N0[n]+1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n++]?0:1);
 } 
 void fG(){
   int           g = (19-N1[n]-N0[n]*4)*4;
   unsigned long a = N2[n]&((unsigned long)15<<g);
   N0[n+1]=N0[n]-1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n++]?0:1);
 } 
 void fE(){
   int           g = (14-N1[n]-N0[n]*4)*4;
   unsigned long a = N2[n]&((unsigned long)15<<g);
   N0[n+1]=N0[n]; N1[n+1]=N1[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N1[n++]?0:1);
 } 
 void fL(){
   int           g = (16-N1[n]-N0[n]*4)*4;
   unsigned long a = N2[n]&((unsigned long)15<<g);
   N0[n+1]=N0[n]; N1[n+1]=N1[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N1[n++]?0:1);
 }

public: 

 fifteenSolver(int n, int i, unsigned long g){N0[0]=n; N1[0]=i; N2[0]=g; N4[0]=0;}
 void Solve(){
   while (not fN()){n=0;++_n;}
   std::cout<<"Solution found in "<<n<<" moves: "; for (int g{1};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl;
 }

}; </lang>

The Task

<lang cpp> int main (){ 

 fifteenSolver start(2,0,0xfe169b4c0a73d852);
 start.Solve();

} </lang>

Output:
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

real    0m0.795s
user    0m0.794s
sys     0m0.000s

F#

<lang fsharp> // A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017 let Nr = [|3;0;0;0;0;1;1;1;1;2;2;2;2;3;3;3|] let Nc = [|3;0;1;2;3;0;1;2;3;0;1;2;3;0;1;2|] let rec Solve n = 

 let rec fN (i,g,e,l,_) = seq {
   let   fI = let n = (11-g-i*4)*4
              let a = (e&&&(15UL<<<n))
              (i+1,g,e-a+(a<<<16),'d'::l,Nr.[(int (a>>>n))] <= i)
   let   fG = let n = (19-g-i*4)*4
              let a = (e&&&(15UL<<<n))
              (i-1,g,e-a+(a>>>16),'u'::l,Nr.[(int (a>>>n))] >= i)
   let   fE = let n = (14-g-i*4)*4
              let a = (e&&&(15UL<<<n))
              (i,g+1,e-a+(a<<<4), 'r'::l,Nc.[(int (a>>>n))] <= g)
   let   fL = let n = (16-g-i*4)*4
              let a = (e&&&(15UL<<<n))
              (i,g-1,e-a+(a>>>4), 'l'::l,Nc.[(int (a>>>n))] >= g)
   let   fZ (n,i,g,e,l) = seq{yield (n,i,g,e,l); if l then yield! fN (n,i,g,e,l)}
   match (i,g,l) with
     |(0,0,'l'::_) -> yield! fZ fI
     |(0,0,'u'::_) -> yield! fZ fE
     |(0,0,_)      -> yield! fZ fI; yield! fZ fE
     |(0,3,'r'::_) -> yield! fZ fI
     |(0,3,'u'::_) -> yield! fZ fL
     |(0,3,_)      -> yield! fZ fI; yield! fZ fL
     |(3,0,'l'::_) -> yield! fZ fG
     |(3,0,'d'::_) -> yield! fZ fE
     |(3,0,_)      -> yield! fZ fE; yield! fZ fG
     |(3,3,'r'::_) -> yield! fZ fG
     |(3,3,'d'::_) -> yield! fZ fL
     |(3,3,_)      -> yield! fZ fG; yield! fZ fL
     |(0,_,'l'::_) -> yield! fZ fI; yield! fZ fL
     |(0,_,'r'::_) -> yield! fZ fI; yield! fZ fE
     |(0,_,'u'::_) -> yield! fZ fE; yield! fZ fL
     |(0,_,_)      -> yield! fZ fI; yield! fZ fE; yield! fZ fL
     |(_,0,'l'::_) -> yield! fZ fI; yield! fZ fG
     |(_,0,'u'::_) -> yield! fZ fE; yield! fZ fG
     |(_,0,'d'::_) -> yield! fZ fI; yield! fZ fE
     |(_,0,_)      -> yield! fZ fI; yield! fZ fE; yield! fZ fG
     |(3,_,'l'::_) -> yield! fZ fG; yield! fZ fL
     |(3,_,'r'::_) -> yield! fZ fE; yield! fZ fG
     |(3,_,'d'::_) -> yield! fZ fE; yield! fZ fL
     |(3,_,_)      -> yield! fZ fE; yield! fZ fG; yield! fZ fL
     |(_,3,'d'::_) -> yield! fZ fI; yield! fZ fL
     |(_,3,'u'::_) -> yield! fZ fL; yield! fZ fG
     |(_,3,'r'::_) -> yield! fZ fI; yield! fZ fG
     |(_,3,_)      -> yield! fZ fI; yield! fZ fL; yield! fZ fG
     |(_,_,'d'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fL
     |(_,_,'l'::_) -> yield! fZ fI; yield! fZ fG; yield! fZ fL
     |(_,_,'r'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fG
     |(_,_,'u'::_) -> yield! fZ fE; yield! fZ fG; yield! fZ fL
     |_            -> yield! fZ fI; yield! fZ fE; yield! fZ fG; yield! fZ fL
 }
 let n = Seq.collect fN n
 match (Seq.tryFind(fun(_,_,n,_,_)->n=0x123456789abcdef0UL)) n with
 |Some(_,_,_,n,_) -> printf "Solution found with %d moves: " (List.length n); List.iter (string >> printf "%s") (List.rev n); printfn ""
 |_               -> Solve (Seq.filter(fun (_,_,_,_,n)->not n) n)

Solve [(2,0,0xfe169b4c0a73d852UL,[],false)] </lang>

Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
Retrieved from "https://rosettacode.org/wiki/15_puzzle_solver?oldid=276425"