Solve the 15 Puzzle (the tile-sliding puzzle) The 15 Puzzle is a famous puzzle involving sliding 15 tiles around on a 4x4 grid. Starting from a random configuration, the goal is to arrange the tiles in the correct order. Here is an example of a solved 15 Puzzle:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15


Each move on the puzzle is of the form Up/Down/Left/Right. The move "Down" consists of sliding the tile that is above the empty spot downward. The move "Right" consists of sliding a tile to the right, into the empty spot. Here is how the board looks after the moves Down and Right.

01 02 03 04
05 06 07 08
09 10    11
13 14 15 12




The goal of this challenge is to write a program that can output the series of moves needed to solve the 15 Puzzle. The winner is the program who solves the five test cases (below) in the fewest total moves. The generated solution does not need to be a perfect solution, it merely has to be better than the competitors. For each individual test case, the program should not take more than ten seconds on a reasonable machine. 

Your program must be able to solve any puzzle that is solvable, I'm just using these five test cases as the scoring.

Your program will receive the unsolved 15 Puzzle as input in the format of a 2D array. The 2D array can be formatted according to the language used, or changed if the language does not have 2D arrays. The first element of the first sub-array will be the number in the upper left, and the last element of the first sub-array will be the number in the upper right. A 0 will be the empty space.

As output, your program should print a list of moves in the order that they need to be performed. Each step should be numbered in order to increase the usability of the results.

EDIT: Based on comments, I will allow output to be in either the form of Down/Up/etc or in the form of the coordinates of the piece to move. As this is not code golf, the most important part is to solve the puzzle.

Some other general rules involve no using an outside source, etc.



Test Case 1

([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])


Example Output:

1: Down
2: Down
3: Down
4: Left
....


Test Case 2

([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])


Test Case 3

([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])


Test Case 4

([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])


Test Case 5

([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])
PyPy, 195 moves, ~12 seconds computation

Computes optimal solutions using IDA* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions:

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

 2  5 13 12
 1  0  3 15
 9  7 14  6
10 11  8  4
Left, Down, Right, Up, Up, Left, Down, Down, Right, Up, Left, Left, Down, Right, Right, Right, Up, Up, Left, Left, Down, Left, Up, Up, Right, Down, Down, Left, Up, Up, Right, Right, Right, Down, Left, Up, Right, Down, Down, Left, Left, Down, Left, Up, Up, Right, Up, Left

 5  2  4  8
10  0  3 14
13  6 11 12
 1 15  9  7
Left, Up, Up, Right, Right, Down, Left, Up, Left, Left, Down, Down, Right, Right, Up, Left, Left, Down, Down, Right, Right, Up, Right, Up, Left, Left, Up, Right, Down, Down, Right, Down, Left, Left, Up, Up, Left, Up

11  4 12  2
 5 10  3 15
14  1  6  7
 0  9  8 13
Down, Left, Down, Right, Up, Left, Left, Left, Down, Down, Right, Right, Right, Up, Left, Left, Left, Down, Right, Right, Up, Left, Up, Up, Left, Down, Down, Right, Down, Right, Up, Up, Right, Up, Left, Left, Left, Down, Right, Right, Right, Up, Left, Down, Left, Down, Left, Up, Up

 5  8  7 11
 1  6 12  2
 9  0 13 10
14  3  4 15
Up, Right, Down, Left, Left, Down, Left, Up, Right, Up, Right, Down, Down, Right, Up, Up, Left, Left, Left, Down, Down, Down, Right, Right, Up, Right, Down, Left, Up, Left, Up, Left, Down, Right, Down, Left, Up, Right, Down, Right, Up, Up, Left, Left, Up


And the code:

import random


class IDAStar:
    def __init__(self, h, neighbours):
        """ Iterative-deepening A* search.

        h(n) is the heuristic that gives the cost between node n and the goal node. It must be admissable, meaning that h(n) MUST NEVER OVERSTIMATE the true cost. Underestimating is fine.

        neighbours(n) is an iterable giving a pair (cost, node, descr) for each node neighbouring n
        IN ASCENDING ORDER OF COST. descr is not used in the computation but can be used to
        efficiently store information about the path edges (e.g. up/left/right/down for grids).
        """

        self.h = h
        self.neighbours = neighbours
        self.FOUND = object()


    def solve(self, root, is_goal, max_cost=None):
        """ Returns the shortest path between the root and a given goal, as well as the total cost.
        If the cost exceeds a given max_cost, the function returns None. If you do not give a
        maximum cost the solver will never return for unsolvable instances."""

        self.is_goal = is_goal
        self.path = [root]
        self.is_in_path = {root}
        self.path_descrs = []
        self.nodes_evaluated = 0

        bound = self.h(root)

        while True:
            t = self._search(0, bound)
            if t is self.FOUND: return self.path, self.path_descrs, bound, self.nodes_evaluated
            if t is None: return None
            bound = t

    def _search(self, g, bound):
        self.nodes_evaluated += 1

        node = self.path[-1]
        f = g + self.h(node)
        if f &gt; bound: return f
        if self.is_goal(node): return self.FOUND

        m = None # Lower bound on cost.
        for cost, n, descr in self.neighbours(node):
            if n in self.is_in_path: continue

            self.path.append(n)
            self.is_in_path.add(n)
            self.path_descrs.append(descr)
            t = self._search(g + cost, bound)

            if t == self.FOUND: return self.FOUND
            if m is None or (t is not None and t &lt; m): m = t

            self.path.pop()
            self.path_descrs.pop()
            self.is_in_path.remove(n)

        return m


def slide_solved_state(n):
    return tuple(i % (n*n) for i in range(1, n*n+1))

def slide_randomize(p, neighbours):
    for _ in range(len(p) ** 2):
        _, p, _ = random.choice(list(neighbours(p)))
    return p

def slide_neighbours(n):
    movelist = []
    for gap in range(n*n):
        x, y = gap % n, gap // n
        moves = []
        if x &gt; 0: moves.append(-1)    # Move the gap left.
        if x &lt; n-1: moves.append(+1)  # Move the gap right.
        if y &gt; 0: moves.append(-n)    # Move the gap up.
        if y &lt; n-1: moves.append(+n)  # Move the gap down.
        movelist.append(moves)

    def neighbours(p):
        gap = p.index(0)
        l = list(p)

        for m in movelist[gap]:
            l[gap] = l[gap + m]
            l[gap + m] = 0
            yield (1, tuple(l), (l[gap], m))
            l[gap + m] = l[gap]
            l[gap] = 0

    return neighbours

def slide_print(p):
    n = int(round(len(p) ** 0.5))
    l = len(str(n*n))
    for i in range(0, len(p), n):
        print(" ".join("{:&gt;{}}".format(x, l) for x in p[i:i+n]))

def encode_cfg(cfg, n):
    r = 0
    b = n.bit_length()
    for i in range(len(cfg)):
        r |= cfg[i] &lt;&lt; (b*i)
    return r


def gen_wd_table(n):
    goal = [[0] * i + [n] + [0] * (n - 1 - i) for i in range(n)]
    goal[-1][-1] = n - 1
    goal = tuple(sum(goal, []))

    table = {}
    to_visit = [(goal, 0, n-1)]
    while to_visit:
        cfg, cost, e = to_visit.pop(0)
        enccfg = encode_cfg(cfg, n)
        if enccfg in table: continue
        table[enccfg] = cost

        for d in [-1, 1]:
            if 0 &lt;= e + d &lt; n:
                for c in range(n):
                    if cfg[n*(e+d) + c] &gt; 0:
                        ncfg = list(cfg)
                        ncfg[n*(e+d) + c] -= 1
                        ncfg[n*e + c] += 1
                        to_visit.append((tuple(ncfg), cost + 1, e+d))

    return table

def slide_wd(n, goal):
    wd = gen_wd_table(n)
    goals = {i : goal.index(i) for i in goal}
    b = n.bit_length()

    def h(p):
        ht = 0 # Walking distance between rows.
        vt = 0 # Walking distance between columns.
        d = 0
        for i, c in enumerate(p):
            if c == 0: continue
            g = goals[c]
            xi, yi = i % n, i // n
            xg, yg = g % n, g // n
            ht += 1 &lt;&lt; (b*(n*yi+yg))
            vt += 1 &lt;&lt; (b*(n*xi+xg))

            if yg == yi:
                for k in range(i + 1, i - i%n + n): # Until end of row.
                    if p[k] and goals[p[k]] // n == yi and goals[p[k]] &lt; g:
                        d += 2

            if xg == xi:
                for k in range(i + n, n * n, n): # Until end of column.
                    if p[k] and goals[p[k]] % n == xi and goals[p[k]] &lt; g:
                        d += 2

        d += wd[ht] + wd[vt]

        return d
    return h




if __name__ == "__main__":
    solved_state = slide_solved_state(4)
    neighbours = slide_neighbours(4)
    is_goal = lambda p: p == solved_state

    tests = [
        (5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12),
        (2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4),
        (5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7),
        (11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13),
        (5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15),
    ]

    slide_solver = IDAStar(slide_wd(4, solved_state), neighbours)

    for p in tests:
        path, moves, cost, num_eval = slide_solver.solve(p, is_goal, 80)
        slide_print(p)
        print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))
        print(cost, num_eval)