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

integer collected = 0 sequence lines = repeat("",5)

procedure print_board(integer last) integer k = 2

   for i=1 to length(board) do
       string this = iff(i=pos?"   ":sprintf("%3d",{board[i]}))
       lines[k] &= this
       if mod(i,4)=0 then k+=1 end if
   end for
   collected += 1
   if collected=6 or last then
       puts(1,join(lines,"\n")&"\n\n")
       lines = repeat("",5)
       collected = 0
   else
       for i=2 to 5 do
           lines[i] &= "      "
       end for
   end if

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      -- (37.5% 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]
       lines[1] = sprintf("thinking... %d boards visited, best score: %d (0=solved):",{dsv,s})
       print_board(1)
   else
       boards = new_boards
   end if

end while

pos = pos0 board = board0 lines[1] = "solved!!: " print_board(0) for i=1 to length(moves) do

   integer mi = moves[i]
   string m = udlr[mi]
   string this = sprintf("move %d, %s:",{i,m})
   lines[1] &= sprintf("%-18s",{this})
   moves[i] = upper(m[1])
   {} = move(mi)
   print_board(i=length(moves))

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>

solved!!:         move 1, left:     move 2, down:     move 3, down:     move 4, left:     move 5, up:
 15 14  1  6       15 14  1  6       15 14  1  6       15     1  6       15  1     6       15  1  4  6
  9 11  4 12        9 11  4 12        9     4 12        9 14  4 12        9 14  4 12        9 14    12
    10  7  3       10     7  3       10 11  7  3       10 11  7  3       10 11  7  3       10 11  7  3
 13  8  5  2       13  8  5  2       13  8  5  2       13  8  5  2       13  8  5  2       13  8  5  2

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

move 12, down:    move 13, left:    move 14, up:      move 15, left:    move 16, up:      move 17, right:
 15  1  4  6       15  1  4  6       15  1  4  6       15  1  4  6       15  1  4  6       15  1  4  6
  9     7 12        9  7    12        9  7  3 12        9  7  3 12        9  7  3 12        9  7  3 12
 10 14  3  2       10 14  3  2       10 14     2       10 14  2          10 14  2  5       10 14  2  5
 13 11  8  5       13 11  8  5       13 11  8  5       13 11  8  5       13 11  8          13 11     8

move 18, right:   move 19, down:    move 20, left:    move 21, left:    move 22, down:    move 23, down:
 15  1  4  6       15  1  4  6       15  1  4  6       15  1  4  6       15  1  4  6       15  1  4
  9  7  3 12        9  7  3 12        9  7  3 12        9  7  3 12        9  7  3           9  7  3  6
 10 14  2  5       10     2  5       10  2     5       10  2  5          10  2  5 12       10  2  5 12
 13    11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8

move 24, right:   move 25, up:      move 26, right:   move 27, up:      move 28, right:   move 29, down:
 15  1     4       15  1  3  4       15  1  3  4       15  1  3  4       15  1  3  4       15  1  3  4
  9  7  3  6        9  7     6        9     7  6        9  2  7  6        9  2  7  6           2  7  6
 10  2  5 12       10  2  5 12       10  2  5 12       10     5 12          10  5 12        9 10  5 12
 13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8

move 30, down:    move 31, left:    move 32, up:      move 33, right:   move 34, up:      move 35, left:
     1  3  4        1     3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4
 15  2  7  6       15  2  7  6       15     7  6          15  7  6        9 15  7  6        9 15  7  6
  9 10  5 12        9 10  5 12        9 10  5 12        9 10  5 12          10  5 12       10     5 12
 13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8

move 36, down:    move 37, left:    move 38, up:      move 39, left:    move 40, up:      move 41, right:
  1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4
  9     7  6        9  7     6        9  7  5  6        9  7  5  6        9  7  5  6        9  7  5  6
 10 15  5 12       10 15  5 12       10 15    12       10 15 12          10 15 12  8       10 15 12  8
 13 14 11  8       13 14 11  8       13 14 11  8       13 14 11  8       13 14 11          13 14    11

move 42, down:    move 43, right:   move 44, down:    move 45, left:    move 46, left:    move 47, up:
  1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4
  9  7  5  6        9  7  5  6        9     5  6        9  5     6        9  5  6           9  5  6  8
 10 15     8       10    15  8       10  7 15  8       10  7 15  8       10  7 15  8       10  7 15
 13 14 12 11       13 14 12 11       13 14 12 11       13 14 12 11       13 14 12 11       13 14 12 11

move 48, up:      move 49, right:   move 50, down:    move 51, right:   move 52, right:   move 53, down:
  1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4        1  2  3  4
  9  5  6  8        9  5  6  8        9  5  6  8        9  5  6  8        9  5  6  8           5  6  8
 10  7 15 11       10  7 15 11       10  7    11       10     7 11          10  7 11        9 10  7 11
 13 14 12          13 14    12       13 14 15 12       13 14 15 12       13 14 15 12       13 14 15 12

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

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