8puzzle solver using A*

That's gonna take long.

This program solves 8 puzzle game (mini version of 15 puzzle) using A* algorithm. Program consists of 2 parts:

• Board.java - which serves as a representation for the board (N-by-N grid, not limited to 9 tiles)

• Solver.java - as the name implies, this class solves the given puzzle (if it is solvable)

Here is the sample 3-by-3 Board (taken from toString()):

4 1 3 
0 2 6 
7 5 8

One issue with this code is that it is painfully slow (I realize that majority of methods take quadratic time, however this is way slower than the spec requires it to be). The problem lies here:
Output from Solver class (# of moves == number of expected moves, time measured in seconds)

# of moves = 5 && # of actual moves 5 & time passed 0.004000
# of moves = 7 && # of actual moves 35 & time passed 0.002000
# of moves = 8 && # of actual moves 9 & time passed 0.000000
# of moves = 9 && # of actual moves 9 & time passed 0.001000
# of moves = 11 && # of actual moves 260 & time passed 0.008000
# of moves = 18 && # of actual moves 6560 & time passed 0.056000
# of moves = 25 && # of actual moves 267431 & time passed 3.963000

I have commented the one with 36 required moves in Solver class's main method, cause it may consume a lot of memory and slow down your machine. Make sure you run from the command line; it perfroms poorly from Eclipse

This code is doing a lot of unnecessary work (basically walking in a circles) until it realizes that this was all waste and only then takes optimal path. You can see it by comparing number of expected moves vs. number of actual moves. My assumption was corroborated by careful debugging session and the problem is that I don't know how to circumvent this issue. Maybe insight into priority function will help:
There are 2 of them, Hamming and Manhattan (Manhattan is preferred, cause it converges faster)
Given the board below, Manhattan is calculated by subtracting deviations of tile from their positions:

```

Your A* is incorrectly implemented

You are using the total number of moves explored as the priority for each search node. See here:

while (!dequeuedBoard.isGoal()) {
        boards = dequeuedBoard.neighbors();
        moves++;

        for (Board board : boards) {
            if (!board.equals(previous) && !previouses.contains(board)) {
                minPQ.add(new SearchNode(board, moves, dequeuedNode));
            }
        }

moves is incremented once per explored node and then used as base cost for the search node. This is incorrect.

You must use the number of moves taken to reach that particular position + heuristic value. This means that you must store the number of moves used to reach a particular SearchNode in the SearchNode.

In other words, you should do this instead :

minPQ.add(new SearchNode(board, dequeuedNode.moves + 1, dequeuedNode));

Refresher of A*

I see some indications that you are not entirely sure of how A* actually works so I'll try to explain.

Consider a graph of nodes and edges where each edge has a non-negative cost associated with it (in some cases edges can have negative costs but I won't cover it here). A* will efficiently find a path from node A to node B with minimal total cost.

What makes A* efficient is that it is "guided", in the sense that it uses domain knowledge in the form of a heuristic to guide it to explore more promising paths first. The heuristic is a function that can give a lower bound on the best possible path between two nodes. Essentially it is an informed, optimistic guess.

Example: Think of a car map. Each node is a city, each edge is a road between two cities, and the cost of the edge is the length of the road. A suitable heuristic could be the straight line distance between two cities because there can be no shorter route. This heuristic will never over estimate the cost but it can grossly underestimate the cost at times.

So if we have a path from A to some intermediary node X and the total cost to get from A to X, and we can guess the remaining cost with the heuristic (without over estimating), then we can estimate the lowest possible cost if we continue on this path by taking the sum of the two.

By repeatedly taking one step along the path with the lowest estimated cost, we will eventually find the shortest route.

Untested example pseudo-code:

class Node{
    class Edge{
        Node destination;
        int cost;
    }
    Collection edges;
}

class Path{
    Node currentNode;
    int costSoFar;
    int estCost;
    List currentPath;

    Path(Node start){
       currentNode = start;
       costSoFar = 0;
       estCost = costSoFar + guessCostLeft();
       currentPath = List.of(start);
    }

    Path(Path path, Edge edge){
        currentNode = edge.destination;
        costSoFar = path.costSoFar + edge.cost;
        estCost = costSoFar + guessCostLeft();
        currentPath = path.currentPath + edge.destination;
    }

    // This is our heuristic!
    int guessCostLeft(){...}
}

Path AStarSolve(Node aStart, Node aEnd, int maxIterations){
    PriorityQueue paths(OrderByEstCost);
    paths.add(new Path(aStart));

    while(maxIterations-- > 0 ){
        Path path = paths.first();
        paths.pop(); // (1)

        if(path.currentNode == aEnd){
            return path; // First found solution is the best
        }
        for(Edge edge : path.currentNode.edges){
            // Explore all edges from this node then.
            paths.add(new Path(path, edge)); // (2)
        }
    }
}

Note0: There are many ways to implement A* wikipedia has one that is slightly different and possibly more efficient but slightly more complicated.

Note1: I used max iterations as termination criteria if no solution is found, you may want to use some other criteria. For example if you know an upper bound on the cost you can use that.

Note2: With some heuristics there may be several paths to the same (non end) node in the paths queue and they may not necessarily be added in the order of cheapest path first due to the heuristic being a guess and may cause nodes to be explored in a sub-optimal order. You may remove paths to the same node, as long as you keep the cheapest one. But removing them may take more time than to just leave them there, measure!

Note3: If your heuristic function is an oracle, i.e. it can always guess the exact remaining cost, then A will find the cheapest path directly. And if the heuristic always guesses 0 (which is an allowed, but bad heuristic), then A will degrade to greedy search. This means, that the closer to the true cost the heuristic can be without over estimating the true cost the faster A* will find the cheapest path.

StackExchange Code Review Q#145876, answer score: 3