3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You might be interested in this. \$\endgroup\$ – coderodde May 13 at 16:06
  • \$\begingroup\$ thx for the link. \$\endgroup\$ – Marten May 13 at 17:04
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ok, thanks. I don't really understand Advice 4. Why I shouldn't store the puzzle state in my Node class? \$\endgroup\$ – Marten May 13 at 16:27
  • 2
    \$\begingroup\$ @Marten You could, but it is not usual way of writing industrial level code. I suggest you use HashMap for storing these pathfinding-related data items. For example, you could have HashMap<Node, Integer> for that purpose. \$\endgroup\$ – coderodde May 13 at 16:56
  • \$\begingroup\$ Ok thx. In my getChildren() method I copy ervery time the board. Is it possible to get rid of it?(otherwise after swaping, list elements would change) \$\endgroup\$ – Marten May 13 at 17:03
  • \$\begingroup\$ @Marten I might be missing something but it doesn't look like you use the previous boards. So only maintain the current board (the one set on the primary class) and just don't copy it. \$\endgroup\$ – Matthew Read May 13 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.