8
\$\begingroup\$

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:

8  1  3 
4     2
7  6  5

For example, tile 8 (the first one) is 3 tiles away from its expected position (2 rows down, 1 column to the right) Tile 1 (the second one) is 1 tile away from its position (1 column to the left)

If we consider the board as a list, then we can calculate Manhattan distance in the following way:

1  2  3  4  5  6  7  8
----------------------        Manhattan = 1 + 2 + 2 + 2 + 3 = 10
1  2  0  0  2  2  0  3

Each number in the top, indicates how the board should be aligned, to be deemed as solved, and numbers below, indicating how many tiles are these numbers away from their expected position. Basically, Manhattan priority function will show us the minimum number of moves are needed to solve the puzzle.

Now priority function of the Board is calculated as its Manhattan distance + number of moves made to reach to that very state. For instance, for the inserted Board, priority will be equal to its Manhattan distance + 0 moves, since no steps were made. For the next neighbor node, which is dequeued, moves will equal to 1 and so on.

So what basically A* star does, it looks at the neighbors of the current Board (+-1 row, +-1 col), dequeues it (of course saving it) and looks for the neighbors of the dequeued Board and so on, until dequeued Board is the goal Board (A* is guaranteed to converge).

You see, when we have two boards with the same Manhattan priorities, PriorityQueue chooses the first one even though it leads to a bad, I would even say catastrophic consequences and surely, as complexity of the puzzle increases, these fallacies add up (the thing that is infinitely obvious to us, humans, doesn't seem to be so for computers) Alternatively, algorithm checks previous Boards, that are stored in PQ (with lower priority functions, due to the small number of moves) and after checking them, without any result to show up, it chooses the right one.

Here comes JUnit 4 tests for both classes:

Here comes the code for 2 classes. P.S Sorry for Javadocs, I couldn't complete them Board.java

import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;


public final class Board {

    private final int[][] tilesCopy;
    private final int N;

    // cache
    private int hashCode = -1;
    private int zeroRow = -1;
    private int zeroCol = -1;
    private Collection<Board> neighbors;
    /*
     * Rep Invariant
     *      tilesCopy.length > 0
     * Abstraction Function
     *      represent single board of 8 puzzle game
     * Safety Exposure
     *      all fields are private and final (except cache variables). In the constructor,
     * defensive copy of tiles[][] (array that is received from the client)
     * is done.
     */
    public Board(int[][] tiles) {
        this.N = tiles.length;
        this.tilesCopy = new int[N][N];
        // defensive copy
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (tiles[i][j] >= 0 && tiles[i][j] < N*N) tilesCopy[i][j] = tiles[i][j];
                else {
                    System.out.printf("Illegal tile value at (%d, %d): "
                                    + "should be between 0 and N^2 - 1.", i, j);
                    System.exit(1);
                }
            }
        }
        checkRep();
    }

    public int tileAt(int row, int col) {
        if (row < 0 || row > N - 1) throw new IndexOutOfBoundsException
            ("row should be between 0 and N - 1");
        if (col < 0 || col > N - 1) throw new IndexOutOfBoundsException
            ("col should be between 0 and N - 1");

        return tilesCopy[row][col];
    }

    public int size() {
        return N; 
    }

    public int hamming() {
        int hamming = 0;
        for (int row = 0; row < this.size(); row++) {
            for (int col = 0; col < this.size(); col++) {
                if (tileAt(row, col) != 0 && tileAt(row, col) != (row*N + col + 1)) hamming++; 
            }
        }
        return hamming;
    }
    // sum of Manhattan distances between tiles and goal
    public int manhattan() {
        int manhattan = 0;

        int expectedRow = 0, expectedCol = 0;
        for (int row = 0; row < this.size(); row++) {
            for (int col = 0; col < this.size(); col++) {
                if (tileAt(row, col) != 0 && tileAt(row, col) != (row*N + col + 1)) {
                    expectedRow = (tileAt(row, col) - 1) / N;
                    expectedCol = (tileAt(row, col) - 1) % N;
                    manhattan += Math.abs(expectedRow - row) + Math.abs(expectedCol - col);
                }
            }
        }
        return manhattan;
    }

    public boolean isGoal() {

        if (tileAt(N-1, N-1) != 0) return false;        // prune

        for (int i = 0; i < this.size(); i++) {
            for (int j = 0; j < this.size(); j++) {
                if (tileAt(i, j) != 0 && tileAt(i, j) != (i*N + j + 1)) return false;
            }
        }

        return true;
    }
    // change i && j' s name
    public boolean isSolvable() {   
        int inversions = 0;

        for (int i = 0; i < this.size() * this.size(); i++) {
            int currentRow = i / this.size();
            int currentCol = i % this.size();

            if (tileAt(currentRow, currentCol) == 0) {
                this.zeroRow = currentRow;
                this.zeroCol = currentCol;
            }

            for (int j = i; j < this.size() * this.size(); j++) {
                int row = j / this.size();
                int col = j % this.size();


                if (tileAt(row, col) != 0 && tileAt(row, col) < tileAt(currentRow, currentCol)) {
                    inversions++;
                }
            }
        }

        if (tilesCopy.length % 2 != 0 && inversions % 2 != 0) return false;
        if (tilesCopy.length % 2 == 0 && (inversions + this.zeroRow) % 2 == 0) return false;

        return true;    
    }



    @Override
    public boolean equals(Object y) {
        if (!(y instanceof Board)) return false;
        Board that = (Board) y;
        if (this.tileAt(N-1, N-1) != that.tileAt(N-1, N-1)) return false;   // why bother checking whole array, if last elements aren't equals
        if (this.size() != that.size()) return false;

        return Arrays.deepEquals(this.tilesCopy, that.tilesCopy);
    }

    @Override
    public int hashCode() { 
        if (this.hashCode != -1) return hashCode;
        // more optimized version(Arrays.hashCode is too slow)?
        this.hashCode = Arrays.deepHashCode(tilesCopy);
        return this.hashCode;
    }

    public Collection<Board> neighbors() {
        if (neighbors != null) return neighbors;
        if (this.zeroRow == -1 && this.zeroCol == -1) findZeroTile();

        neighbors = new HashSet<>();

        if (zeroRow - 1 >= 0)           generateNeighbor(zeroRow - 1, true);
        if (zeroCol - 1 >= 0)           generateNeighbor(zeroCol - 1, false);
        if (zeroRow + 1 < this.size())  generateNeighbor(zeroRow + 1, true);
        if (zeroCol + 1 < this.size())  generateNeighbor(zeroCol + 1, false);

        return neighbors;
    }

    private void findZeroTile() {
        outerloop:
            for (int i = 0; i < this.size(); i++) {
                for (int j = 0; j < this.size(); j++) {
                    if (tileAt(i, j) == 0) {
                        this.zeroRow = i;       // index starting from 0
                        this.zeroCol = j;
                        break outerloop;
                    }
                }
            }
    }
    private void generateNeighbor(int toPosition, boolean isRow) {
        int[][] copy = Arrays.copyOf(this.tilesCopy, tilesCopy.length);
        if (isRow)  swapEntries(copy, zeroRow, zeroCol, toPosition, zeroCol);
        else        swapEntries(copy, zeroRow, zeroCol, zeroRow, toPosition);

        neighbors.add(new Board(copy));
    }


    private void swapEntries(int[][] array, int fromRow, int fromCol, int toRow, int toCol) {
        int i = array[fromRow][fromCol];
        array[fromRow][fromCol] = array[toRow][toCol];
        array[toRow][toCol] = i;
    }

    public String toString() {
        StringBuilder s = new StringBuilder(4 * N * N);     // optimization?
//      s.append(N + "\n");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                s.append(String.format("%2d ", tileAt(i, j)));
            }
            s.append("\n");
        }
        return s.toString();
    }

    private void checkRep() {
        assert tilesCopy.length > 0;
    }   
}

Solver.java

import java.util.HashSet;
import java.util.Set;
import java.util.Objects;

import board.Board;
import java.util.Stack;
import java.util.PriorityQueue;


public class Solver {
    private final PriorityQueue<SearchNode> minPQ;
    private int moves = 0;
    private SearchNode finalNode;       
    private Stack<Board> boards;

    /* Rep Invariant
     *      TODO
     * Abstraction Function
     *      TODO
     * Safety Exposure Argument
     *      TODO
     */

    /**
     * find a solution to the initial board (using the A* algorithm)
     * @param initial
     * @throws NullPointerException
     * @throws IllegalArgumentException
     */
    public Solver(Board initial) {
        Objects.requireNonNull("board can't be null");
        if (!initial.isSolvable()) throw new IllegalArgumentException("Unsolvable puzzle");

        // this.initial = initial;
        this.minPQ = new PriorityQueue<SearchNode>(initial.size() + 10);    // magic number :>

        Set<Board> previouses = new HashSet<Board>(50);
        Board dequeuedBoard = initial;
        Board previous = null;
        SearchNode dequeuedNode = new SearchNode(initial, 0, null);
        Iterable<Board> boards;

        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));
                }
            }

            previouses.add(previous);
            previous = dequeuedBoard;
            dequeuedNode = minPQ.poll();
            dequeuedBoard = dequeuedNode.current;
        }
        finalNode = dequeuedNode;
    }

    // min number of moves to solve initial board
    public int moves() {
        if (boards != null) return boards.size()-1;
        solution();
        return boards.size() - 1;
    }

    public Iterable<Board> solution() {
        if (boards != null) return boards;
        boards = new Stack<Board>();
        SearchNode pointer = finalNode;
        while (pointer != null) {
            boards.push(pointer.current);
            pointer = pointer.previous;
        }
        return boards;
    }

    private class SearchNode implements Comparable<SearchNode> {
        private final int priority;
        private final SearchNode previous;
        private final Board current;


        public SearchNode(Board current, int moves, SearchNode previous) {
            this.current = current;
            this.previous = previous;
            this.priority = moves + current.manhattan();
        }

        @Override
        public int compareTo(SearchNode that) {
            int cmp = this.priority - that.priority;
            if      (cmp < 0) return -1;
            else if (cmp > 0) return 1;
            else return 0;
        }


    }
    public static void main(String[] args) {
        int[][] tiles5 = {{4, 1, 3}, 
                        {0, 2, 6}, 
                        {7, 5, 8}};

        int[][] tiles7 = {{1, 2, 3}, 
                        {0, 7, 6}, 
                        {5, 4, 8}};


        int[][] tiles8 = {{2, 3, 5}, 
                        {1, 0, 4}, 
                        {7, 8, 6}};

        int[][] tiles9 = {{2, 0, 3, 4}, 
                    {1, 10, 6, 8}, 
                    {5, 9, 7, 12}, 
                    {13, 14, 11, 15}};

        int[][] tiles11 = {{1, 0, 2}, 
                            {7, 5, 4}, 
                            {8, 6, 3}};

        int[][] tiles18 = {{5, 6, 2}, 
                        {1, 8, 4}, 
                        {7, 3, 0}};


                // answer will be here, compare w/ other

        int[][] tiles25 = {{2, 8, 5}, 
                          {3, 6, 1}, 
                          {7, 0, 4}};

        int[][] tiles36 = {{5, 3, 1, 4}, 
                        {10, 2, 8, 7}, 
                        {14, 13, 0, 11}, 
                        {6, 9, 15, 12}};


        double start5 = System.currentTimeMillis();
        Board board5 = new Board(tiles5);
        Solver solve5 = new Solver(board5); 
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n, ", solve5.moves(), solve5.moves, (System.currentTimeMillis() - start5) / 1000);

        double start7 = System.currentTimeMillis();
        Board board7 = new Board(tiles7);
        Solver solve7 = new Solver(board7);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve7.moves(), solve7.moves, (System.currentTimeMillis() - start7) / 1000);

        double start8 = System.currentTimeMillis();
        Board board8 = new Board(tiles8);
        Solver solve8 = new Solver(board8);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve8.moves(), solve8.moves, (System.currentTimeMillis() - start8) / 1000);

        double start9 = System.currentTimeMillis();
        Board board9 = new Board(tiles9);
        Solver solve9 = new Solver(board9);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve9.moves(), solve9.moves, (System.currentTimeMillis() - start9) / 1000);

        double start11 = System.currentTimeMillis();
        Board board11 = new Board(tiles11);
        Solver solve11 = new Solver(board11);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve11.moves(), solve11.moves, (System.currentTimeMillis() - start11) / 1000);

        double start18 = System.currentTimeMillis();
        Board board18 = new Board(tiles18);
        Solver solve18 = new Solver(board18);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve18.moves(), solve18.moves, (System.currentTimeMillis() - start18) / 1000);
//    
        double start25 = System.currentTimeMillis();
        Board board25 = new Board(tiles25);
        Solver solve25 = new Solver(board25);
        System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve25.moves(), solve25.moves, (System.currentTimeMillis() - start25) / 1000);

        // double start36 = System.currentTimeMillis();
        // Board board36 = new Board(tiles36);
        // Solver solve36 = new Solver(board36);
        // System.out.printf("# of moves = %d && # of actual moves %d & time passed %f\n", solve36.moves(), solve36.moves, (System.currentTimeMillis() - start36) / 1000);
    }

}
\$\endgroup\$
1
  • \$\begingroup\$ For reference, you could take a look at this GitHub repository. \$\endgroup\$
    – coderodde
    Commented Nov 4, 2016 at 15:24

3 Answers 3

Reset to default
3
+50
\$\begingroup\$

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<Edge> edges;
}

class Path{
    Node currentNode;
    int costSoFar;
    int estCost;
    List<Node> 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<Path> 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.

\$\endgroup\$
3
  • \$\begingroup\$ Not sure if I understood you properly. SearchNode class calculates priority in the following way: this.priority = moves + current.manhattan(); which is the number of moves taken to reach that particular position + heuristic value. \$\endgroup\$
    – user118482
    Commented Nov 6, 2016 at 11:02
  • \$\begingroup\$ @jmstfv see edit \$\endgroup\$
    – Emily L.
    Commented Nov 6, 2016 at 18:29
  • \$\begingroup\$ @jmstfv by moves taken to reach that particular position it is meant the depth of the search tree at the current node. Look at how you calculate the moves variable, it is the current amount of dequeued nodes this far. And there is your problem. \$\endgroup\$
    – Emily L.
    Commented Nov 6, 2016 at 20:09
2
\$\begingroup\$

I haven't even looked at Board.java: all of these points related to the Solver constructor.

Emily's point is the most important one, but to add to it:

How many times can a single board end up in minPQ? The answer should be one, but I don't think it is because the loop through the neighbours enqueues a new node if the neighbour hasn't previously been dequeued without checking whether there's a node for the neighbour already in the queue. It is conventional to check whether there's an existing node, and if so to reduce its priority if applicable. Otherwise you can end up multiplying the running time by a factor of something close to the average number of neighbours.

Check your scopes. E.g.

    Iterable<Board> boards;

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

        ...
    }
    finalNode = dequeuedNode;
}

The scope of boards is the while loop, so by pushing in the definition you improve readability. (And since it's only used once, and in a simple expression, you could even eliminate it entirely).

Keep it simple. What is the purpose of previous?

    Board previous = null;
    ...
    while (!dequeuedBoard.isGoal()) {
        ...
        for (Board board : boards) {
            if (!board.equals(previous) && !previouses.contains(board)) {
                ...
            }
        }

        previouses.add(previous);
        previous = dequeuedBoard;
        ...
    }

This would be just as correct (or arguably more correct), and simpler:

    while (!dequeuedBoard.isGoal()) {
        previouses.add(dequeuedBoard);
        ...
        for (Board board : boards) {
            if (!previouses.contains(board)) {
                ...
            }
        }

        ...
    }

(As an aside, I don't think that previouses is a great name. English doesn't inflect adjectives, and it's not a standard "nouning". Now that the name previous is no longer used, I'd refactor previouses renaming it to previous).

On the subject of KISS, tracking the current node and the current board independently seems like a potential source of maintainance errors. I'd be inclined to just track the current node and to access the board via the node.

The question of how much work a constructor should do is controversial. Some people would be very upset at the amount of work done in the Solver constructor. I'm not going to take sides, but I wanted to make you aware that it's a point to consider.

\$\endgroup\$
1
\$\begingroup\$

Advice 1

class Board {
...
}

In my opinion, Tile is a better name for Board. (After all, the game is called sliding tile puzzle.)

Advice 2

import java.util.Objects;
import java.util.Stack;
import java.util.TreeSet;

These are not used in Board.java. Why not clean the code and remove them?

Advice 3

I would go around having an interface representing (any) heuristic function for the sliding tile puzzle, and its implementation as a separate class.

Advice 4

In Solver constructor:

Objects.requireNonNull("board can't be null");

should be

Objects.requireNonNull(initial, "board can't be null");

Advice 5

You can find the (correct) pseudocode for A* here. Also, you will need to implement a priority queue "wrapper":

final class HeapEntry implements Comparable<HeapEntry> {

    private final Board board;
    private final int distance; // The priority key.

    public HeapEntry(Board board, int distance) {
        this.board = board;
        this.distance = distance;
    }

    public int getBoard() {
        return board;
    }

    public int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(HeapEntry o) {
        return Integer.compare(distance, o.distance);
    }
}

When you have the above, let OPEN be a PriorityQueue<HeapEntry>.

Advice 6

Since 15-puzzle has no shortest paths of no more length than around 90 transitions, and each weight/heuristic distance in the sliding tile puzzle is a non-negative integer, you can use a Dial's heap. The idea behind that data structure is that you maintain internally an array \$A\$ of length around 100. Next, each array component \$A[i]\$ is the head of a collision chain (just like in a hash table) of all the boards with estimate \$i\$ (which is, of course, an integer). Now, whenever, say, popping the head of the priority queue, scan the \$A\$ starting from index 0 and return the first board you encounter. It's easy to code and has (sometimes) better performance than a binary heap.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.