Your task is to write a program that finds a solution in the fewest moves possible single moves 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


 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 two solutions, of fifty-two moves:

rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd

see: Pretty Print of Optimal Solution

Finding either one, or both is an acceptable result.


Extra credit.
Solve the following problem:

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



Related Task

 15 puzzle game
 A* search algorithm


-- 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