I have this program that solves a \$(n^2 - 1)\$-puzzles for general \$n\$. I have three solvers:BidirectionalBFSPathFinderAStarPathFinderDialAStarPathFinder AStarPathFinder relies on java.util.PriorityQueue and DialAStarPathFinder uses so called Dial's heap which is a very natural choice in this setting: all priorities are non-negative integers and the set of all possible priorities is small (should be \$\{ 0, 1, 2, \dots, k \}\$, where \$k \approx 100\$ for \$n = 4\$). DialHeap.java:package net.coderodde.puzzle;import java.util.HashMap;import java.util.Map;import java.util.NoSuchElementException;/** * This class implements Dial's heap. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) * @param <E> the type of the actual elements being stored. */public class DialHeap<E> {    private static final int INITIAL_CAPACITY = 64;    private static final class DialHeapNode<E> {        E element;        int priority;        DialHeapNode<E> prev;        DialHeapNode<E> next;        DialHeapNode(E element, int priority) {            this.element = element;            this.priority = priority;        }    }    private final Map<E, DialHeapNode<E>> map = new HashMap<>();    private DialHeapNode<E>[] table = new DialHeapNode[INITIAL_CAPACITY];    private int size;    private int minimumPriority = Integer.MAX_VALUE;    public void add(E element, int priority) {        checkPriority(priority);        if (map.containsKey(element)) {            return;        }        ensureCapacity(priority);        DialHeapNode<E> newnode = new DialHeapNode(element, priority);        newnode.next = table[priority];        if (table[priority] != null) {            table[priority].prev = newnode;        }        if (minimumPriority > priority) {            minimumPriority = priority;        }        table[priority] = newnode;        map.put(element, newnode);        ++size;    }    public void decreasePriority(E element, int priority) {        checkPriority(priority);        // Get the actual heap node storing 'element'.        DialHeapNode<E> targetHeapNode = map.get(element);        if (targetHeapNode == null) {            // 'element' not in this heap.            return;        }        // Read the current priority of the 'element'.        int currentPriority = targetHeapNode.priority;        if (priority >= currentPriority) {            // No improvement possible.            return;        }        unlink(targetHeapNode);        targetHeapNode.prev = null;        targetHeapNode.next = table[priority];        targetHeapNode.priority = priority;        if (table[priority] != null) {            table[priority].prev = targetHeapNode;        }        if (minimumPriority > priority) {            minimumPriority = priority;        }        table[priority] = targetHeapNode;    }    public E extractMinimum() {        if (size == 0) {            throw new NoSuchElementException(Extracting from an empty heap.);        }        DialHeapNode<E> targetNode = table[minimumPriority];        table[minimumPriority] = targetNode.next;        if (table[minimumPriority] != null) {            table[minimumPriority].prev = null;        } else {            if (size == 1) {                // Extracting the very last element. Reset to maximum value.                minimumPriority = Integer.MAX_VALUE;            } else {                minimumPriority++;                while (minimumPriority < table.length                        && table[minimumPriority] == null) {                    ++minimumPriority;                }            }        }        --size;        E element = targetNode.element;        map.remove(element);        return element;    }    public int size() {        return size;    }    private void ensureCapacity(int capacity) {        if (table.length <= capacity) {            int newCapacity = Integer.highestOneBit(capacity) << 1;            DialHeapNode<E>[] newTable = new DialHeapNode[newCapacity];            System.arraycopy(table, 0, newTable, 0, table.length);            System.out.println(table.length +  ->  + newCapacity);            table = newTable;        }    }     private void checkPriority(int priority) {        if (priority < 0) {            throw new IllegalArgumentException(                    Heap does not handle negative priorities. Received:  +                     priority);        }    }    private void unlink(DialHeapNode<E> node) {        int priority = node.priority;        if (node.next != null) {            node.next.prev = node.prev;        }         if (node.prev != null) {            node.prev.next = node.next;        } else {            table[priority] = node.next;        }    }}PuzzleNode.java:package net.coderodde.puzzle;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Random;/** * This class implements a puzzle node for {@code n^2 - 1} - puzzle. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) */public class PuzzleNode {    private final byte[][] matrix;    private byte emptyTileX;    private byte emptyTileY;    private int hashCode;    public PuzzleNode(int n) {        this.matrix = new byte[n][n];        byte entry = 1;        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                matrix[y][x] = entry++;            }        }        matrix[n - 1][n - 1] = 0;        hashCode = Arrays.deepHashCode(matrix);        emptyTileX = (byte)(n - 1);        emptyTileY = (byte)(n - 1);    }    private PuzzleNode(PuzzleNode node) {        int n = node.matrix.length;        this.matrix = new byte[n][n];        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                this.matrix[y][x] = node.matrix[y][x];            }        }        this.hashCode = Arrays.deepHashCode(this.matrix);        this.emptyTileX = node.emptyTileX;        this.emptyTileY = node.emptyTileY;    }    @Override    public boolean equals(Object o) {        if (o == null) {            return false;        }        if (!o.getClass().equals(this.getClass())) {            return false;        }        PuzzleNode other = (PuzzleNode) o;        if (this.hashCode != other.hashCode) {            return false;        }        return Arrays.deepEquals(this.matrix, other.matrix);    }    @Override    public int hashCode() {        return hashCode;    }    public PuzzleNode up() {        if (emptyTileY == 0) {            return null;        }        PuzzleNode ret = new PuzzleNode(this);        ret.matrix[emptyTileY][emptyTileX] = this.matrix[emptyTileY - 1]                                                        [emptyTileX];        ret.matrix[--ret.emptyTileY][emptyTileX] = 0;        ret.hashCode = Arrays.deepHashCode(ret.matrix);        return ret;    }    public PuzzleNode right() {        if (emptyTileX == this.matrix.length - 1) {            return null;        }        PuzzleNode ret = new PuzzleNode(this);        ret.matrix[emptyTileY][emptyTileX] = this.matrix[emptyTileY]                                                        [emptyTileX + 1];        ret.matrix[emptyTileY][++ret.emptyTileX] = 0;        ret.hashCode = Arrays.deepHashCode(ret.matrix);        return ret;    }    public PuzzleNode down() {        if (emptyTileY == matrix.length - 1) {            return null;        }        PuzzleNode ret = new PuzzleNode(this);        ret.matrix[emptyTileY][emptyTileX] = this.matrix[emptyTileY + 1]                                                        [emptyTileX];        ret.matrix[++ret.emptyTileY][emptyTileX] = 0;        ret.hashCode = Arrays.deepHashCode(ret.matrix);        return ret;    }    public PuzzleNode left() {        if (emptyTileX == 0) {            return null;        }        PuzzleNode ret = new PuzzleNode(this);        ret.matrix[emptyTileY][emptyTileX] = this.matrix[emptyTileY]                                                        [emptyTileX - 1];        ret.matrix[emptyTileY][--ret.emptyTileX] = 0;        ret.hashCode = Arrays.deepHashCode(ret.matrix);        return ret;    }    public List<PuzzleNode> children() {        List<PuzzleNode> childrenList = new ArrayList<>(4);        insert(childrenList, up());        insert(childrenList, right());        insert(childrenList, down());        insert(childrenList, left());        return childrenList;    }    public List<PuzzleNode> parents() {        List<PuzzleNode> parentList = new ArrayList<>(4);        insert(parentList, up());        insert(parentList, right());        insert(parentList, down());        insert(parentList, left());        return parentList;    }    public int getDegree() {        return matrix.length;    }    public byte get(int x, int y) {        return matrix[y][x];    }    public PuzzleNode randomSwap(Random rnd) {        final PuzzleNode newNode = new PuzzleNode(this);        int degree = this.matrix.length;        int sourceX = rnd.nextInt(degree);        int sourceY = rnd.nextInt(degree);        for (;;) {            if (matrix[sourceY][sourceX] == 0) {                sourceX = rnd.nextInt(degree);                sourceY = rnd.nextInt(degree);            } else {                break;            }        }        for (;;) {            int targetX = sourceX;            int targetY = sourceY;            switch (rnd.nextInt(4)) {                case 0:                    --targetX;                    break;                case 1:                    ++targetX;                    break;                case 2:                    --targetY;                    break;                case 3:                    ++targetY;                    break;            }            if (targetX < 0 || targetY < 0) {                continue;            }            if (targetX >= degree || targetY >= degree) {                continue;            }            if (matrix[targetY][targetX] == 0) {                continue;            }            byte tmp = newNode.matrix[sourceY][sourceX];            newNode.matrix[sourceY][sourceX] = newNode.matrix[targetY][targetX];            newNode.matrix[targetY][targetX] = tmp;            newNode.hashCode = Arrays.deepHashCode(newNode.matrix);            return newNode;        }    }    @Override    public String toString() {        StringBuilder sb = new StringBuilder();        sb.append([)          .append(emptyTileX)          .append(, )          .append(emptyTileY)          .append(]\n);        int n = this.matrix.length;        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                sb.append(String.format(%2d, matrix[y][x])).append(' ');            }            if (y < n - 1) {                sb.append('\n');            }        }        return sb.toString();    }    private static void insert(List<PuzzleNode> list, PuzzleNode node) {        if (node != null) {            list.add(node);        }    }}PathFinder.java:package net.coderodde.puzzle;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Map;/** * This interface defines the API for path finding algorithms and a couple of  * methods for constructing shortest paths. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) */public interface PathFinder {    public List<PuzzleNode> search(PuzzleNode source, PuzzleNode target);    default List<PuzzleNode> tracebackPath(PuzzleNode target,                                            Map<PuzzleNode,                                                PuzzleNode> parentMap) {        List<PuzzleNode> path = new ArrayList<>();        PuzzleNode current = target;        while (current != null) {            path.add(current);            current = parentMap.get(current);        }        Collections.<PuzzleNode>reverse(path);        return path;    }    default List<PuzzleNode>         tracebackPath(PuzzleNode touchNode,                      Map<PuzzleNode, PuzzleNode> PARENTSA,                      Map<PuzzleNode, PuzzleNode> PARENTSB) {        List<PuzzleNode> path = tracebackPath(touchNode, PARENTSA);        PuzzleNode current = PARENTSB.get(touchNode);        while (current != null) {            path.add(current);            current = PARENTSB.get(current);        }        return path;    }}BidirectionalBFSPathFinder.java:package net.coderodde.puzzle;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.Deque;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Objects;/** * This class implements bidirectional breadth-first search. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) */public class BidirectionalBFSPathFinder implements PathFinder {    @Override    public List<PuzzleNode> search(PuzzleNode source, PuzzleNode target) {        Objects.requireNonNull(source, The source node is null.);        Objects.requireNonNull(target, The target node is null.);        if (source.equals(target)) {            // Bidirectional algorithms do not handle correctly the case where            // the source and target nodes are the same.            returnTarget(target);        }        Deque<PuzzleNode> QUEUE_A = new ArrayDeque<>();        Deque<PuzzleNode> QUEUE_B = new ArrayDeque<>();        Map<PuzzleNode, PuzzleNode> PARENTS_A = new HashMap<>();        Map<PuzzleNode, PuzzleNode> PARENTS_B = new HashMap<>();        Map<PuzzleNode, Integer> DISTANCE_A = new HashMap<>();        Map<PuzzleNode, Integer> DISTANCE_B = new HashMap<>();        QUEUE_A.addLast(source);        QUEUE_B.addLast(target);        PARENTS_A.put(source, null);        PARENTS_B.put(target, null);        DISTANCE_A.put(source, 0);        DISTANCE_B.put(target, 0);        int bestCost = Integer.MAX_VALUE;        PuzzleNode touchNode = null;        while (!QUEUE_A.isEmpty() && !QUEUE_B.isEmpty()) {            if (touchNode != null) {                if (bestCost < DISTANCE_A.get(QUEUE_A.getFirst()) +                               DISTANCE_B.get(QUEUE_B.getFirst())) {                    return tracebackPath(touchNode, PARENTS_A, PARENTS_B);                }            }            if (QUEUE_A.size() < QUEUE_B.size()) {                PuzzleNode current = QUEUE_A.removeFirst();                if (DISTANCE_B.containsKey(current)) {                    int cost = DISTANCE_A.get(current) +                                DISTANCE_B.get(current);                    if (bestCost > cost) {                        bestCost = cost;                        touchNode = current;                    }                }                for (PuzzleNode child : current.children()) {                    if (!DISTANCE_A.containsKey(child)) {                        DISTANCE_A.put(child, DISTANCE_A.get(current) + 1);                        PARENTS_A.put(child, current);                        QUEUE_A.addLast(child);                    }                }            } else {                PuzzleNode current = QUEUE_B.removeFirst();                if (DISTANCE_A.containsKey(current)) {                    int cost = DISTANCE_A.get(current) +                               DISTANCE_B.get(current);                    if (bestCost > cost) {                        bestCost = cost;                        touchNode = current;                    }                }                for (PuzzleNode parent : current.parents()) {                    if (!DISTANCE_B.containsKey(parent)) {                        DISTANCE_B.put(parent, DISTANCE_B.get(current) + 1);                        PARENTS_B.put(parent, current);                        QUEUE_B.addLast(parent);                    }                }            }        }        return Collections.<PuzzleNode>emptyList();    }    private List<PuzzleNode> returnTarget(PuzzleNode target) {        List<PuzzleNode> path = new ArrayList<>(1);        path.add(target);        return path;    }}AStarPathFinder.java:package net.coderodde.puzzle;import java.util.Collections;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Objects;import java.util.PriorityQueue;import java.util.Queue;import java.util.Set;/** * This class implements A* pathfinding algorithm. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) */public class AStarPathFinder implements PathFinder {    private int[] targetXArray;    private int[] targetYArray;    private void processTarget(PuzzleNode target) {        int n = target.getDegree();        this.targetXArray = new int[n * n];        this.targetYArray = new int[n * n];        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                byte entry = target.get(x, y);                targetXArray[entry] = x;                targetYArray[entry] = y;            }        }    }    @Override    public List<PuzzleNode> search(PuzzleNode source, PuzzleNode target) {        Objects.requireNonNull(source, The source node is null.);        Objects.requireNonNull(target, The target node is null.);        processTarget(target);        Queue<NodeHeapEntry> OPEN = new PriorityQueue<>();        Set<PuzzleNode> CLOSED = new HashSet<>();        Map<PuzzleNode, PuzzleNode> PARENTS = new HashMap<>();        Map<PuzzleNode, Integer> DISTANCE = new HashMap<>();        OPEN.add(new NodeHeapEntry(source, 0));        DISTANCE.put(source, 0);        PARENTS.put(source, null);        while (!OPEN.isEmpty()) {            PuzzleNode current = OPEN.remove().node;            if (current.equals(target)) {                return tracebackPath(target, PARENTS);            }            if (CLOSED.contains(current)) {                continue;            }            CLOSED.add(current);            for (PuzzleNode child : current.children()) {                if (!CLOSED.contains(child)) {                    int g = DISTANCE.get(current) + 1;                    if (!DISTANCE.containsKey(child)                            || DISTANCE.get(child) > g) {                        PARENTS.put(child, current);                        DISTANCE.put(child, g);                        OPEN.add(new NodeHeapEntry(child, g + h(child)));                    }                }            }        }        return Collections.<PuzzleNode>emptyList();    }    private int h(PuzzleNode node) {        int n = node.getDegree();        int distance = 0;        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                byte entry = node.get(x, y);                if (entry != 0) {                    distance += Math.abs(x - targetXArray[entry]) +                                Math.abs(y - targetYArray[entry]);                }            }        }        return distance;    }    private static final class NodeHeapEntry     implements Comparable<NodeHeapEntry> {        PuzzleNode node;        int priority;        NodeHeapEntry(PuzzleNode node, int priority) {            this.node = node;            this.priority = priority;        }        @Override        public int compareTo(NodeHeapEntry o) {            return Integer.compare(priority, o.priority);        }    }}DialAStarPathFinder.java:package net.coderodde.puzzle;import java.util.Collections;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Objects;import java.util.Set;/** * This class implements A* pathfinding algorithm using Dial's heap. *  * @author Rodion rodde Efremov * @version 1.6 (Nov 16, 2015) */public class DialAStarPathFinder implements PathFinder {    private int[] targetXArray;    private int[] targetYArray;    private void processTarget(PuzzleNode target) {        int n = target.getDegree();        this.targetXArray = new int[n * n];        this.targetYArray = new int[n * n];        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                byte entry = target.get(x, y);                targetXArray[entry] = x;                targetYArray[entry] = y;            }        }    }    @Override    public List<PuzzleNode> search(PuzzleNode source, PuzzleNode target) {        Objects.requireNonNull(source, The source node is null.);        Objects.requireNonNull(target, The target node is null.);        processTarget(target);        DialHeap<PuzzleNode> OPEN = new DialHeap<>();        Set<PuzzleNode> CLOSED = new HashSet<>();        Map<PuzzleNode, PuzzleNode> PARENTS = new HashMap<>();        Map<PuzzleNode, Integer> DISTANCE = new HashMap<>();        OPEN.add(source, h(source));        DISTANCE.put(source, 0);        PARENTS.put(source, null);        while (OPEN.size() > 0) {            PuzzleNode current = OPEN.extractMinimum();            if (current.equals(target)) {                return tracebackPath(target, PARENTS);            }            if (CLOSED.contains(current)) {                continue;            }            CLOSED.add(current);            for (PuzzleNode child : current.children()) {                if (!CLOSED.contains(child)) {                    int g = DISTANCE.get(current) + 1;                    if (!DISTANCE.containsKey(child)) {                        PARENTS.put(child, current);                        DISTANCE.put(child, g);                        OPEN.add(child, g + h(child));                    } else if (DISTANCE.get(child) > g) {                        PARENTS.put(child, current);                        DISTANCE.put(child, g);                        OPEN.decreasePriority(child, g + h(child));                    }                }            }        }        return Collections.<PuzzleNode>emptyList();    }    private int h(PuzzleNode node) {        int n = node.getDegree();        int distance = 0;        for (int y = 0; y < n; ++y) {            for (int x = 0; x < n; ++x) {                byte entry = node.get(x, y);                if (entry != 0) {                    distance += Math.abs(x - targetXArray[entry]) +                                Math.abs(y - targetYArray[entry]);                }            }        }        return distance;    }}PerformanceDemo.java:import java.util.List;import java.util.Random;import net.coderodde.puzzle.AStarPathFinder;import net.coderodde.puzzle.BidirectionalBFSPathFinder;import net.coderodde.puzzle.DialAStarPathFinder;import net.coderodde.puzzle.PathFinder;import net.coderodde.puzzle.PuzzleNode;public class PerformanceDemo {    public static void main(String[] args) {        int SWAPS = 16;        PuzzleNode target = new PuzzleNode(4);        PuzzleNode source = target;        long seed = System.nanoTime();        Random random = new Random(seed);        for (int i = 0; i < SWAPS; ++i) {            source = source.randomSwap(random);        }        System.out.println(Seed:  + seed);        profile(new BidirectionalBFSPathFinder(), source, target);        profile(new AStarPathFinder(), source, target);        profile(new DialAStarPathFinder(), source, target);    }    private static void profile(PathFinder finder,                                PuzzleNode source,                                 PuzzleNode target) {        long startTime = System.nanoTime();        List<PuzzleNode> path = finder.search(source, target);        long endTime = System.nanoTime();        System.out.printf(%s in %.2f milliseconds. Path length: %d\n,                          finder.getClass().getSimpleName(),                          (endTime - startTime) / 1e6,                          path.size());    }}DialHeapTest.java:package net.coderodde.puzzle;import java.util.NoSuchElementException;import org.junit.Test;import static org.junit.Assert.*;import org.junit.Before;public class DialHeapTest {    private DialHeap<Integer> heap;    @Before    public void before() {        heap = new DialHeap<>();    }    @Test    public void test() {        for (int i = 9, size = 0; i >= 0; --i, ++size) {            assertEquals(size, heap.size());            heap.add(i, i);            assertEquals(size + 1, heap.size());        }        int i = 0;        while (heap.size() > 0) {            assertEquals(Integer.valueOf(i++), heap.extractMinimum());        }        try {            heap.extractMinimum();            fail(Heap should have thrown NoSuchElementException.);        } catch (NoSuchElementException ex) {        }        // 9 -> 14        // 8 -> 13        // ...        // 0 -> 5        for (i = 9; i >= 0; --i) {            heap.add(i, i + 5);        }        for (i = 5; i < 10; ++i) {            heap.decreasePriority(i, i - 5);        }        for (i = 0; i < 5; ++i) {            assertEquals(Integer.valueOf(i + 5), heap.extractMinimum());        }        for (i = 0; i < 5; ++i) {            assertEquals(Integer.valueOf(i), heap.extractMinimum());        }        // Test that the heap expands its internal array whenever exceeding its        // size.        for (i = 0; i < 1000; ++i) {            heap.add(i, i);        }        heap.add(10_000, 32_000);        while (heap.size() > 0) {            heap.extractMinimum();        }        heap.add(1, 1);        heap.add(0, 0);        heap.decreasePriority(0, 10);        assertEquals(Integer.valueOf(0), heap.extractMinimum());        assertEquals(Integer.valueOf(1), heap.extractMinimum());        assertEquals(0, heap.size());        heap.add(1, 1);        heap.add(0, 2);        heap.add(0, 0);        assertEquals(Integer.valueOf(1), heap.extractMinimum());        assertEquals(Integer.valueOf(0), heap.extractMinimum());    }}The best figure I got so far:Seed: 665685156966189BidirectionalBFSPathFinder in 6929.62 milliseconds. Path length: 33AStarPathFinder in 458.56 milliseconds. Path length: 33DialAStarPathFinder in 104.86 milliseconds. Path length: 33Any critique is much appreciated.
Comparing puzzle solvers in Java
java;algorithm;pathfinding;sliding tile puzzle;priority queue
GeneralThis is a perfect example as multiple implementations of an interface make it very robust. So I only have only little to address.NormalizationBreak your implementations of the search(.., ..)-methods into smaller pieces By doing so try to preserve/improve locality, avoid rampantly parameter declaration and avoid passing working references. Especially your search()-method of the BidirectionalBFSPathFinder is very long. Extracting methods and introducing inner working classes should help.Multiple return statements, break, continueIf you experience difficulties by extracting methods or other classes then maybe multiple return statements within a method are the problem. Try to have only one return statement per method at the end. This will make sure that your code can be refactored and extended easily.break and continue cause the same problems. Avoid them in general and search other structures that preserve a well-defined control flow. Often break is used after checking a condition. This condition should be where it supposed to be: The loop header/footer. If you have multiple break statements the breaking conditions are spread all over the place. But they should all be at ONE place.default methods in interfacesDo not use default methods in interfaces to substitute the introduction of an abstract class. As they are public scope these methods are accessable to any client and confuses him/her about the usage. Introduce an abstract class where you provide general functionality for every concrete implementation of PathFinder and extend it (AbstractPathFinder). Then you get rid of the public scope and make it protected so subclass cann access these utility methods.Your interface will then look as clean as heaven:public interface PathFinder {    public List<PuzzleNode> search(PuzzleNode source, PuzzleNode target);}