7
\$\begingroup\$

By N-by-N puzzles I mean f.e. a 3x3 sliding puzzle with one blank space (so a 8-puzzle) or a 4x4 sliding puzzle (so a 15-puzzle). When I try to solve certain puzzles some take no time but others take to much time to the point that I run out of memory. I think it's due to how I calculate the manhattan distance.

Below you see the Board class, an instance of this class holds a puzzle in the variable tiles.

The methods getRow and getCol is used to get the the row and column of a certain value. Then I can calculate the Manhattan distance with the method manhattan.

Could someone tell me how I can optimize this code so that my A*-search algorithm works faster?

public class Board {

    private int[][] tiles;
    private int N;

    // construct a board from an N-by-N array of tiles
    public Board(int[][] tiles) {
        this.tiles = tiles;
        N = tiles.length;
    }

    // return sum of Manhattan distances between blocks and goal
    public int manhattan() {
        int count = 0;
        int expected = 0;

        for (int row = 0; row < tiles.length; row++) {

            for (int col = 0; col < tiles[row].length; col++) {

                int value = tiles[row][col];
                expected++;

                if (value != 0 && value != expected) {
                    // Manhattan distance is the sum of the absolute values of
                    // the horizontal and the vertical distance
                    count += Math.abs(row
                            - getRow(getFinalState().tiles, value))
                            + Math.abs(col
                                    - getCol(getFinalState().tiles, value));
                }
            }
        }

        return count;
    }

    // helper to get a board in final state
    public Board getFinalState() {
        int[][] finalArray = new int[N][N];
        int value = 0;

        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                value++;
                if ((col + 1 == N) && (row + 1 == N)) {
                    finalArray[row][col] = 0;
                } else {
                    finalArray[row][col] = value;
                }

            }
        }

        Board finalState = new Board(finalArray);

        return finalState;
    }

    // helper to get the column of a value.
    public int getCol(int[][] a, int value) {
        for (int row = 0; row < a.length; row++) {
            for (int col = 0; col < a[row].length; col++) {
                if (a[row][col] == value) {
                    return col;
                }
            }
        }
        return -1;
    }

    // helper to get the row of a value.
    public int getRow(int[][] a, int value) {
        for (int row = 0; row < a.length; row++) {
            for (int col = 0; col < a[row].length; col++) {
                if (a[row][col] == value) {
                    return row;
                }
            }
        }
        return -1;
    }   
}

I've add a snippet of my code that I think is slowing down my A*-path search. It's code that I use to find the neighbors of a certain Board.

// return a Collection of all neighboring board positions
public Collection<Board> neighbors() {
    Collection<Board> ns = new ArrayList<Board>();

    for (int row = 0; row < N; row++) {
        for (int col = 0; col < tiles[row].length; col++) {
            if (tiles[row][col] == 0) {

                if (row > 0) {
                    Board neighbor = new Board(copyArray(this.tiles));
                    neighbor.swap(row, col, row - 1, col);
                    ns.add(neighbor);
                }
                if (row < N - 1) {
                    Board neighbor = new Board(copyArray(this.tiles));
                    neighbor.swap(row, col, row + 1, col);
                    ns.add(neighbor);
                }
                if (col > 0) {
                    Board neighbor = new Board(copyArray(this.tiles));
                    neighbor.swap(row, col, row, col - 1);
                    ns.add(neighbor);
                }
                if (col < N - 1) {
                    Board neighbor = new Board(copyArray(this.tiles));
                    neighbor.swap(row, col, row, col + 1);
                    ns.add(neighbor);
                }

                // exit for-loop because there is only one zero
                break;
            }
        }
    }

    return ns;
}

I think it is not the best practice that I copy the array of the board to create new neighbors. I do this because when I didn't copied the array and then swapped elements then the original array was also affected. So I needed an array with no references and that is my way of doing that. Any better way to handle this case?

// helper to copy an array so there are no references
public int[][] copyArray(int[][] a) {
    int[][] copy = new int[a.length][a.length];

    for (int row = 0; row < tiles.length; row++) {
        for (int col = 0; col < tiles[row].length; col++) {
            copy[row][col] = a[row][col];
        }
    }

    return copy;
}

I added the puzzle that makes me run out of memory:

hard-puzzle

\$\endgroup\$
  • \$\begingroup\$ I might be wrong, but it looks like there are 42 steps needed. My A* (which is probably buggy) expanded 349686 nodes. \$\endgroup\$ – maaartinus Apr 11 '15 at 21:30
  • \$\begingroup\$ @maaartinus Tomorow morning I'll place it on github and yes it should be 42 steps! \$\endgroup\$ – anon Apr 11 '15 at 21:56
  • \$\begingroup\$ No problem.... make sure you read the paragraph "A more important optimization you may have missed" of my answer. There are other puzzle solvers posted here and I'll post mine soon, too. \$\endgroup\$ – maaartinus Apr 12 '15 at 8:03
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – anon Apr 12 '15 at 9:30
  • \$\begingroup\$ A List has damn slow lookup. Implement equals and hashCode and use a HashSet. My code is pretty terrible at the moment, but here you are. You need Lombok and Guava to run it. You'll also miss @Nullable and Dout, just drop them (or replace the latter by System.out). \$\endgroup\$ – maaartinus Apr 12 '15 at 16:41
5
\$\begingroup\$

There are two important speed improvements I see at first glance.

First of all, call getFinalState() only once. That method does a bit of work, and there's no need to call that twice for each tile you loop through.

This leads us to the following:

    public int manhattan() {
        int count = 0;
        int expected = 0;
        Board finalState = getFinalState();

        for (int row = 0; row < tiles.length; row++) {
            for (int col = 0; col < tiles[row].length; col++) {
                int value = tiles[row][col];
                expected++;
                if (value != 0 && value != expected) {
                    count += Math.abs(row
                            - getRow(finalState.tiles, value))
                            + Math.abs(col
                                    - getCol(finalState.tiles, value));
                }
            }
        }
        return count;
    }

This already should provide quite a bit of speed-up.


Secondly, your getRow and getCol methods are a bit slow as well. Especially considering that they are only used on the getFinalState() board. One way to speed such methods up generally is to store a Map<Integer, Position> where Position is a pair of x and y values. The key in this map is the value of a position, so for example the value 12 is at row 1 and column 2 can be:

Map<Integer, Position> valueMap = new HashMap<>();
valueMap.put(12, new Position(1, 2));

As they are only called for the final state board though, you can calculate the rows and columns mathematically:

public int getCol(int value) {
    return (value - 1) % N;
}

public int getRow(int value) {
    return (value - 1) / N;
}

This should result in a big speed improvement.


neighbors() method:

This method is slow because a) You're using a loop to find the gap b) You are storing the results in a Collection.

Solutions:

  • Let a Board store the empty position in a variable or two, such as int freeRow, int freeColumn
  • Create your own Iterator<Board> implementation that is able to iterate through the possible boards without storing a reference to all of them.
\$\endgroup\$
  • \$\begingroup\$ Thank you for the quick response. Your getCol and getRow method don't take a final state as parameter, so I guess I shouldn't use a final state at all? Because those are the only methods I use it for. \$\endgroup\$ – Stanko Apr 11 '15 at 15:41
  • \$\begingroup\$ I have just tested your getCol and getRow without the final state and it worked. I thought it would work much faster but to my dissapointment it runs slower, a puzzle that I ran in 0.5 seconds was now 10 seconds. I find it very hard to understand because your way looks far more cleaner and simple. Weird. \$\endgroup\$ – Stanko Apr 11 '15 at 15:54
  • \$\begingroup\$ I also tested your first tip to declare the final state in the for loop and that definitely helped. \$\endgroup\$ – Stanko Apr 11 '15 at 16:00
  • \$\begingroup\$ @Michiel I noticed I did a typo in my getRow method, it should be using division there and not modulo (getCol should use modulo). Make sure your implementation of those methods are correct. \$\endgroup\$ – Simon Forsberg Apr 11 '15 at 16:07
  • \$\begingroup\$ @Michiel Because of the way the final state looks, you don't need to use the final state at all, no. The final state is in a way hard-coded into the getCol and getRow methods. \$\endgroup\$ – Simon Forsberg Apr 11 '15 at 16:08
4
\$\begingroup\$

Warning

The array copying optimization is important for big puzzles. For a 4x4 one, it saves maybe half the memory, so it's hardly worth it. OTOH you need no array as all the data fit in a single long (I'm gonna post such a thing for a review).

Copying arrays

Your

Board neighbor = new Board(copyArray(this.tiles));

is a big problem for bigger boards. You copy the whole array and you do this for each node of your search tree. This means a lot of memory and a lot of time. You need some optimizing trick.

If you can guarantee1 that the array tiles never change after the Board is created, then you can reuse them. Java 2D arrays are nothing but an array of arrays, so if you want to swap two elements in a row, you can reuse all n-1 other rows and copy only the one containing the swapped elements.

And if you want to swap two elements in a column, the situation is similar, except for that you can reuse n-2 rows only. Anyway, for big puzzles your memory consumption reduces by factor n.

So just replace your copyArray by two methods copyArrayAndSwapRow and copyArrayAndSwapCol.

Complexity note

My idea is simple and will surely help. However, given that up to 80 moves are necessary for 4x4 puzzle, I agree fully with Gareth Rees saying that finding the optimum solution is too hard and that A* is not a good choice.

Explanation

A 2D array looks like

a = {
  {1, 2},
  {3, 4}
}

To create a modified copy

b = {
  {2, 1},
  {3, 4}
}

you can use the statement

b = {a[0], {3, 4}};

which means that a[0] gets shared with b. What gets allocated is the 1D array {3, 4} and a 1D array of pointers. No 2D structure gets allocated.

Look at this image and thing about sharing arrays: 2D array

A more important optimization you may have missed

There are a lot of ways to come back to a node which can lead to expanding it again and again. Using a set of already visited nodes prevents this. My code solves your "hard" instance in 0.7 s.


1 This is always possible and immutable objects are just fantastic. Instead of modifying the array when doing a move, you simply create another one. This costs some memory, but allows conserve memory by sharing. Here, the gains are big.

\$\endgroup\$
  • \$\begingroup\$ Hello, I'm not really following you. By reusing all n-1 other rows then I'm still copying the other array right? I don't yet see the difference. Could you provide a code example of your copyArrayAndSwapRow please? \$\endgroup\$ – Stanko Apr 11 '15 at 17:21
  • \$\begingroup\$ @Michiel See my update. if you want to swap two elements in the first row, you need to copy the first row and the blue pointer array only. 2*n work instead of n*n. However, I see now that you're having a problem with a tiny puzzle... so forget this optimization, your problem is A*, using a good heuristics you could find (non-optimal) solutions for huge problems... there's little point for saving with 4x4. \$\endgroup\$ – maaartinus Apr 11 '15 at 17:36
2
\$\begingroup\$

It's not entirely clear from your question what you mean by "N-by-N puzzles", but I'm going to assume that you mean sliding puzzles similar to the 15 puzzle.

In the 15 puzzle, each move only changes the position of two of the tiles (one of them being the blank tile). All the other tiles stay fixed, and these two tiles only change their distance from their correct place by ±1. So you could cache the sum of Manhattan distances in the board object and update it after each move.

However, I doubt that this is all that big a deal. More likely the problem is that you are using the A* search algorithm. The trouble with A* for this kind of puzzle is that it searches for the best (shortest) solution to the puzzle, and that means storing all the positions it has visited so that it can backtrack. There are a lot of positions (10,461,394,944,000 in the case of the 4×4 version) and A* may need to visit a significant number of them in order to prove that it has found the shortest solution.

Unless you really do need the shortest solution, you may find it helpful to switch to a different search algorithm. See the discussion in §6 of this answer.

Update

In the comments, Simon André Forsberg disputed my claims about the effectiveness of the A* algorithm in solving the 15 puzzle. I recommend reading Adrian Brüngger, "Solving Hard Combinatorial Optimization Problems in Parallel: Two Case Studies", which discusses in detail the difficulty of solving the 15 puzzle (see pages 79ff). Brüngger used the branch and bound algorithm with the Manhattan distance heuristic and a pre-generated table of move sequences up to length 14. One would expect this to perform at least as well as A*, and likely better. Nonetheless the table on p. 98 shows that there are positions for which this algorithm has to expand hundreds of billions of search nodes.

A* might still be acceptable if the hard instances were sufficiently rare. To see if that's the case, I instrumented the program in this answer so that it records the number of nodes visited by the A* search.

For \$ n = 10, 20, \dotsc \$ I generated ten random puzzles by making \$ n \$ random moves from a solved position, and found the one whose solution visited the most nodes:

>>> test = lambda n: puzzle15_solve(Position(4, 4).shuffled(n))
>>> for n in range(10, 100, 10):
...     print(n, max(test(n) for _ in range(10))
10 43
20 234
30 6042
40 16885
50 46090
60 925974

The case for \$ n = 70 \$ is still running as I type this answer, having visited more than 10 million nodes. So it looks as though hard instances are relatively easy to find.

\$\endgroup\$
  • \$\begingroup\$ With a good heuristic function, I don't think A* is the problem. It's very few of those 10^12 positions that are actually evaluated in A*. \$\endgroup\$ – Simon Forsberg Apr 11 '15 at 16:10
  • \$\begingroup\$ @SimonAndréForsberg: I disagree. See Adrian Brüngger's PhD thesis, pp. 79ff. Try your A* solver on one of the hard instances on page 98! \$\endgroup\$ – Gareth Rees Apr 11 '15 at 16:29
  • \$\begingroup\$ Okay, good point. For some really hard instances, A* is indeed not optimal. \$\endgroup\$ – Simon Forsberg Apr 11 '15 at 16:53

Your Answer

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