Breadth-First search in Java

Question

Hi

I am having to run a breadth-first search in Java for an assignment. I have a 5x5 grid of tiles (24 in total - 1 tile is left 'blank'). The point of the search is to rearrange the tiles by moving the 'blank' up, down, left or right to eventually rearrange the tiles into the correct order.

To do this search, I have created an Arraylist 'queue'. I have a method that takes the state at index 0 of this arraylist, finds each of the legal moves that can follow and then adds them each to the end of the arraylist.

In theory, this continues until the 'goalstate' is eventually found. The problem is that when I run the search, the 'queue' arraylist just continues to get bigger and bigger. Today I left it running for hours and still the solution had not been found.

This suggests that maybe I have gone about this solution the wrong way and there is a much better way for me to do a breadth-first search in Java. I know my solution does work (eventually) as when I use a start state that isn't too different from the goalstate, it doesn't take too long to find the right path. However, I have been given a start state to use, which unfortunately, is nowhere close to the goalstate!!!

Any hints or tips would be much appreciated!

Answer 1

While it's probably not within the scope of your assignment, there is an algorithm for solving this type of puzzle. Basically, there are a two moves that work for every line except the last two, and a two moves that work for the last two lines. Using this approach gets you a much faster solution.

Unfortunately, since this is an assignment, you are no doubt expected to do brute force searching.

Answer 2

At first glance, it would seem that you may end up with duplicate states and hence cycles in your graph. You may need to look into some way to identify if two states are the same and if you've already visited one before.

EDIT: Putting aside the algorithmic restrictions, perhaps there is a formula to move block X in position Y to position Z without distrubing any other tiles. Given this you can just compute all of the transformations required. I'm just musing about the problem now.

Answer 3

I have done the 'brute search' - the problem is, with a 5x5 grid there are SO many combinations that it just takes forever. I left it running whilst I went to work...8 hours later, it was still going, the queue arraylist size was up to 100k different states and my pc sounded like it was going to overheat and explode lol

I know my code works (eventually, like I said) so I would be happy to submit it. I'm just worried about the time it takes to find a solution and wondered whether there is a better approach I could take, other than using an arraylist to create a queue.

Answer 4

First of all, I would definitely be using an actual Queue object instead of an ArrayList. Here's the Java API page on the Queue interface: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - you can see on that page that there are many implementors of Queue, if you don't know what to choose, a simple LinkedList will do. ArrayList will have a huge performance hit because it is only fast deleting from the end, if you delete from anywhere else in the array it has to shift EVERYTHING down one (SLOW!). You'd be enqueuing at the end and dequeuing at the start, therefore SLOW!

Now you didn't explicitly mention that you are dequeuing items (removing them) after you're done with them so I presume you are, because that would be one reason.

Do you have to specifically use breadth-first search? If I calculated right, there are 25! (factorial) combinations, so that's 15511210043330985984000000 combinations, which theoretically means if you're doing a breadth-first search, your algorithm is not likely to ever finish. Is depth-first search not allowed? If you must use breadth-first search, the only way to make it go faster would be to prune off the states which could not possibly lead to an optimal solution. Not sure how you would go about that.

Answer 5

I think the idea for this exercise is for you to realize that a depth-first search is a better approach to this particular puzzle.

Answer 6

Breadth-first search without duplicate checking is definately going to give you results like the ones you are seeing. In fact, it's fairly trivial to prove that the algorithm as you have implemented it will never terminate. Feel free to wait for it though... :-)

What you need is an ancillary data structure (preferably a Set) to store pre-examined positions. Thus, part of your code will look like the following:

public Queue<Position> queue = new LinkedList<Position>();
public Set<Position> done = new HashSet<Position>();

public Position[] findPath(Position start, Position goal) {
    if (done.contains(start)) return null;

    done.add(start);
    // add subsequent states to `queue`
    ...
}

As mentioned in other answers, depth-first search is a much better solution in this case. Assuming that the goal position is reachable, it should yield exponentially superior search times for all but the most contrived of positions.

Answer 7

I have to actually write code for both. So I am about to move onto depth first search. Before I did it, I just wanted to make sure I wasn't going to be laughed out of my course for producing code that took forever and a day to find a solution!!!!!!!

Answer 8

You didn't say whether you check this or not, but it sounds like you're not pruning cycles.

First, suppose that instead of representing moves as moving the blank square in some direction, you instead supplied the tile number that was moved. (It's guaranteed to be unique.) Now suppose a legal move is "3" - moving tile #3 into the empty space. The result is a new board layout. A legal move from there is to move tile 3 again, and now you're back where you started.

Slider puzzles can easily have larger cycles. If there's a 2x2 grid with 1-2-3-empty in it, then a valid sequence of moves is 1-2-3-1-2-3-1-2-3-1-2-3 - which sends you back to the beginning.

If your search does not check for and prune duplicate boards, the breadth-first search will still terminate (provided there are no bugs, and there's not a parity error(?) making your board unsolvable) - a correct solution exists that is N moves in length, and you'll take finite time to process every sequence of K moves, so you'll eventually get to N, and your solution. However, the time for each move length increases exponentially (up to 4 moves from each board). You're probably thrashing on memory.

Unfortunately, the brute force approach to checking for duplicate board states is to store every board as you arrive at it, which will also use up memory fast - though perhaps not as fast as your current method. It might be satisfactory, in fact, for a mere 5x5 board.

Answer 9

Perhaps a goal-directed depth-first search. Start by solving 9 edge tiles, reducing the puzzle to a 4x4 grid. Then solve the 7 edge tiles of that, reducing to a 3x3 grid which should be easy pickings for your original algorithm.

Answer 10

The way I am doing it at the moment is as follows:

• 2 Arraylists; Queue and Visited
• The start state is automatically added to the Visited arraylist
• All possible legal moves from the start start are obtained and each compared to those stored in the Visited arraylist.
• Those legal moves that do not create a 'visited' state are added to the Queue.
• The state held at index 0 of the arraylist is taken, and the process repeats itself.

I see from previous answers that I should probably change the arraylists into a different collection. But I am checking that states are not duplicated.

Answer 11

Okay the next thing is, if I were to do your visited list, I would use a Set (probably a TreeSet) which would automatically sort the states so that searching to see whether a new state has been visited before would be a lot faster.

All you'd need to do is make your state class implement the Comparable interface. (hopefully you already had expected something like this and made it a class). If you don't know already, using the compareTo method of this interface, you define the sorting order of the objects, which of course would be used by the visited Set. From there you could set up the compareTo method to work like a string comparison except with your tiles.

So just to make it clear, if each tile were assigned a letter, and the tiles in each state were listed out, we might have this:

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

Naturally state 1 would come first in the order. So just extrapolate that compareTo mechanism to work for tiles to tiles (I'm sure your tiles have IDs or indexes or something don't they?) and you'll have a sorted visited list. Then when you called visited.contains(state) the program will be able to calculate very quickly whether a state has been visited or not.