N-puzzle solver using A* search

Question

I have written a Java program to solve a N-puzzle with A* search and manhattan distance. My program can solve every 8-puzzle I have tested under 1 second, but it can't solve a 15-puzzle after 30 minutes. How can I improve performance? Here a short example output:

6  2  1 
0  4  3 
5  8  7 

6  2  1 
4  0  3 
5  8  7   
....

Solution length: 23
Time: 0.165308527

SlidingPuzzle.java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.PriorityQueue;
import java.util.Comparator;

public class SlidingPuzzle {

    private int size;
    private int puzzle[][];
    private final int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private final int l_moves = moves.length;

    public SlidingPuzzle(int puzzle[][]) {
        this.puzzle = puzzle;
        this.size = puzzle.length;
        aStar();
    }

    class Node {

        int puzzle[][];
        int blankX, blankY;
        Node previous;
        int f, h, g;


        public Node(Node previous, int puzzle[][]) {
            this.previous = previous;
            this.puzzle = puzzle;

            // init start node with blankX, blankY and manhattan distance
            if(previous == null) {
                for (int x = 0; x < size; x++) {
                    for (int y = 0; y < size; y++) {

                        int n = puzzle[x][y];

                        if (n == 0) {
                            blankX = x;
                            blankY = y;
                        }else {
                            int x1 = (n - 1) / size;
                            int y1 = (n - 1) % size;
                            this.h += Math.abs(x - x1) + Math.abs(y - y1);
                        }

                    }
                }
            }
        }

        private boolean inBoard(int x, int y) {
            return (x >= 0 && y >= 0 && x < size && y < size);
        }

        private void swapNumbers(int x1, int y1, int x2, int y2) {
            int tmp = puzzle[x1][y1];
            puzzle[x1][y1] = puzzle[x2][y2];
            puzzle[x2][y2] = tmp;
        }

        /*
            from a boardstate to a childstate, manhattan distance can only change by
            +1 or -1, so I don't need to calculate the manhattan distance for the whole board.
         */
        public ArrayList<Node> getChildren() {
            ArrayList<Node> children = new ArrayList<>();

            for (int i = 0; i < l_moves; i++) {

                if (inBoard(blankX + moves[i][0], blankY + moves[i][1])) {

                    int n1 = puzzle[blankX + moves[i][0]][blankY + moves[i][1]];
                    int m1 = calcManhattan(blankX + moves[i][0], (n1 - 1) / size, blankY + moves[i][1],  (n1 - 1) % size);

                    swapNumbers(blankX, blankY, blankX + moves[i][0], blankY + moves[i][1]);

                    int copy[][] = new int[size][size];
                    for (int j = 0; j < size; j++) {
                        copy[j] = puzzle[j].clone();
                    }

                    int n2 = copy[blankX][blankY];
                    int x2 = (n2 - 1) / size;
                    int y2 = (n2 - 1) % size;

                    Node child = new Node(this, copy);
                    child.blankX = this.blankX + moves[i][0];
                    child.blankY = this.blankY + moves[i][1];

                    int m2 = calcManhattan(blankX, x2, blankY, y2);
                    int nm;

                    if(m1 < m2) {
                        nm = 1;
                    }else {
                        nm = -1;
                    }

                    child.h = this.h + nm;
                    children.add(child);

                    swapNumbers(blankX, blankY, blankX + moves[i][0], blankY + moves[i][1]);
                }
            }
            return children;
        }

        public int calcManhattan(int x1, int x2, int y1, int y2) {
            return Math.abs(x1 - x2) + Math.abs(y1 -y2);
        }

        @Override
        public boolean equals(Object o) {
            Node node = (Node) o;
            return Arrays.deepEquals(puzzle, node.puzzle);
        }
    }

    class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node n1, Node n2) {
            return Integer.compare(n1.f, n2.f);
        }
    }

    private void printBoard(int[][] board) {

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {

                String l = "";
                if (board[i][j] < 10) {
                    l = " ";
                }
                System.out.print(l + board[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
    }

    private void reconstructPath(Node current) {
        Stack<Node> path = new Stack<>();
        path.push(current);

        int l = 0;
        while (current.previous != null) {
            current = current.previous;
            path.push(current);
            l++;
        }

        while (!path.isEmpty()) {
            Node n = path.pop();
            printBoard(n.puzzle);
        }

        System.out.println("Solution length: " + l);
    }

    private void aStar() {

        Node start = new Node(null, puzzle);
        Comparator<Node> nodeComparator = new NodeComparator();

        ArrayList<Node> closedList = new ArrayList<>();
        PriorityQueue<Node> openList = new PriorityQueue<>(nodeComparator);

        openList.add(start);

        while (!openList.isEmpty()) {

            Node current = openList.poll();
            closedList.add(current);

            if (current.h == 0) {
                reconstructPath(current);
                break;
            }

            ArrayList<Node> children = current.getChildren();

            for (Node child : children) {

                if (closedList.contains(child) || openList.contains(child) && child.g >= current.g) {
                    continue;
                }

                child.g = current.g + 1;
                child.f = child.g + child.h;

                if(openList.contains(child)){
                    openList.remove(child);
                    openList.add(child);
                }else {
                    openList.add(child);
                }
            }

        }

    }

    public static void main(String[] args) {

        int puzzle[][] =   {{6, 2, 1},
                            {0, 4, 3},
                            {5, 8, 7}};
        long start = System.nanoTime();
        new SlidingPuzzle(puzzle);
        long stop = System.nanoTime();

        double time = (stop - start) / 1000000000.0;

        System.out.println("Time: " +time);
    }
}

Any help is really appreciated.

Answer 1

Advice 1: l_moves

1. The name l_moves is ain't good at all. Consider numberOfMoves.
2. Since it is only read, make it a constant. Even better, it is customary in Java to name the constants with capital case. For this particular case, I suggest you rename l_moves

private static final int NUMBER_OF_MOVES = 4;

Advice 2: class SlidingPuzzle

I suggest you rename it to, say, SlidingPuzzleSolver.

Advice 3: class Node

I suggest you take it out of SlidingPuzzle and make a dedicated .java file for it.

Advice 4: Do not store search state in the actual puzzle nodes

Node previous;
int f, h, g;

Advice 5: implement hashCode

Implementing hashCode of SlidingPuzzle.Node makes it possible for storing the puzzle nodes in a, say, HashSet or HashMap as a key.

Advice 6: on printBoard

Why not override toString for Node?

Advice 7: on reconstructPath

I suggest you construct the shortest path and return it to the caller instead of printing to console output. I had this in mind:

private List<Node> reconstructPath(Node current) {
    Deque<Node> deque = new ArrayDeque<>();
    int l = 0;

    while (current.previous != null) {
        current = current.previous;
        deque.addFirst(current); // Amortized O(1) for the ArrayDeque
        l++;
    }

    for (Node node : deque) {
        printBoard(node.puzzle);
    }

    //System.out.println("Solution length: " + l);
    return new ArrayList<>(deque);
}

Advice 8: ArrayList as the closed list

No, no, no and no. contains for a any JDK List runs in linear time. HashSet could do the same in \$\Theta(1)\$. For that to happen, go back to Advice 5.