15 puzzle solver

15 puzzle solver is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Your task is to write a program that solves the Fifteen Puzzle Game in the fewest number of moves.
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.

Phix

Brute force width-first search, probably not quite optimal, since the scoring algorithm may trim some better paths from the search space.
Shows first solution found. No multi-tile moves. <lang Phix>constant udlr = {"up", "down", "left", "right"} sequence board = tagset(15)&0 integer pos = 16

procedure print_board()

   for i=1 to length(board) do
       puts(1,iff(i=pos?"   ":sprintf("%3d",{board[i]})))
       if mod(i,4)=0 then puts(1,"\n") end if
   end for
   puts(1,"\n")

end procedure

function move(integer d) integer valid = 0 integer stick = 0

   for k=1 to 8 by 2 do
       if board[k]!=k then exit end if
       if board[k+1]!=k+1 then exit end if
       stick = k+1
   end for
   integer new_pos = pos+{+4,-4,+1,-1}[d]
   if new_pos>=1 and new_pos<=16
   and (mod(pos,4)=mod(new_pos,4) -- same col, or row:
    or floor((pos-1)/4)=floor((new_pos-1)/4)) then
       {board[pos],board[new_pos]} = {board[new_pos],0}
       valid = pos>stick and new_pos>stick
       pos = new_pos
   end if
   return {valid,stick}

end function

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

function score(sequence board) integer res = 0, pos, act_pos

   for i=1 to 15 do
       pos = posns[i]
       act_pos = find(pos,board)
       res += (abs(mod(pos,4)-mod(act_pos,4))+
               abs(floor((pos-1)/4)-floor((act_pos-1)/4)))*10*pos
   end for
   return res

end function

if 0 then

   for i=1 to 5555555 do {}=move(rand(4)) end for      -- (25% are likely invalid)

else

   board = {15,14, 1, 6,
             9,11, 4,12,
             0,10, 7, 3,
            13, 8, 5, 2}
   pos = find(0,board)

end if atom t0 = time() integer pos0 = pos, s, valid, stick sequence board0 = board, boards = {{0,score(board),{},board,pos}}, new_boards, moves integer visited = new_dict() while 1 do

   new_boards = {}
   for i=1 to length(boards) do
       for c=1 to 4 do
           {?,?,moves,board,pos} = boards[i]
           {valid,stick} = move(c)
           if valid and getd_index(board,visited)=0 then
               moves &= c
               s = score(board)
               if s=0 then exit end if
               new_boards = append(new_boards,{8-stick,s,moves,board,pos})
               setd(board,0,visited)
           end if
       end for
       if s=0 then exit end if
   end for
   if s=0 then exit end if
   if length(new_boards)>16384 then
       boards = sort(new_boards)[1..16384]
       integer dsv = dict_size(visited)
       {?,s,{},board,pos} = boards[1]
       printf(1,"thinking... %d boards visited, best score: %d (0=solved):\n",{dsv,s})
       print_board()
   else
       boards = new_boards
   end if

end while

pos = pos0 board = board0 printf(1,"\n\nsolved!!:\n=========\n") print_board() for i=1 to length(moves) do

   integer mi = moves[i]
   string m = udlr[mi]
   printf(1,"move %d, %s:\n",{i,m})
   moves[i] = upper(m[1])
   {} = move(mi)
   print_board()

end for printf(1,"solved in %d moves (%d boards visited, %s)\n",{length(moves),dict_size(visited),elapsed(time()-t0)}) printf(1,"moves: %s\n",{moves}) {} = wait_key()</lang>

Output:

thinking... 39204 boards visited, best score: 1910 (0=solved):
 15     1  6
  8 14 11  4
  9 10  3 12
 13  5  7  2

thinking... 71666 boards visited, best score: 1760 (0=solved):
    15  1  6
  8 14 11  4
  9 10  3 12
 13  5  7  2

thinking... 103082 boards visited, best score: 1840 (0=solved):
 15  1  6
  8 14 11  4
  9 10  3 12
 13  5  7  2

<snip>

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

move 44, down:
  1  2  3  4
  9     5  6
 10  7 15  8
 13 14 12 11

move 45, left:
  1  2  3  4
  9  5     6
 10  7 15  8
 13 14 12 11

move 46, left:
  1  2  3  4
  9  5  6
 10  7 15  8
 13 14 12 11

move 47, up:
  1  2  3  4
  9  5  6  8
 10  7 15
 13 14 12 11

move 48, up:
  1  2  3  4
  9  5  6  8
 10  7 15 11
 13 14 12

move 49, right:
  1  2  3  4
  9  5  6  8
 10  7 15 11
 13 14    12

move 50, down:
  1  2  3  4
  9  5  6  8
 10  7    11
 13 14 15 12

move 51, right:
  1  2  3  4
  9  5  6  8
 10     7 11
 13 14 15 12

move 52, right:
  1  2  3  4
  9  5  6  8
    10  7 11
 13 14 15 12

move 53, down:
  1  2  3  4
     5  6  8
  9 10  7 11
 13 14 15 12

move 54, left:
  1  2  3  4
  5     6  8
  9 10  7 11
 13 14 15 12

move 55, left:
  1  2  3  4
  5  6     8
  9 10  7 11
 13 14 15 12

move 56, up:
  1  2  3  4
  5  6  7  8
  9 10    11
 13 14 15 12

move 57, left:
  1  2  3  4
  5  6  7  8
  9 10 11
 13 14 15 12

move 58, up:
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15

solved in 58 moves (1330046 boards visited, 49.11s)
moves: LDDLUULURRDDLULURRDLLDDRURURDDLURULDLULURDRDLLUURDRRDLLULU