15 puzzle solver

From Rosetta Code
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[edit]

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.

--
-- demo\rosetta\Solve15puzzle.exw
-- ==============================
--
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 -- (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]
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()
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