Breadth First Search (rush hour) - Linked list queue contains duplicates of the same board

Question

Hello stackoverflow users, I am attempting to implement a breadth first search on the classic rush hour game. However, I am having a problem with the queue. Before I add something to the queue, I printed out what each board looks like:

[-, 0, 0, -, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

0 1 0
[-, -, 0, 0, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

0 2 0
[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

However, when I print out the queue, it comes out like this:

[-, -, 0, 0, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

The segment of code which I printed out these boards:

for (int i = car.getY() + 1; i < (5 - car.getLen()) + 1; i++) {
    if (isSafeHorizontal(b, car, i)) {
        Board copy = new Board(b.boardVehicles, b.moves, nextCar);
        copy.moveVehicle(car.getX(), i, b.currentCar);
        for (int a = 0;  a< queue.size(); a++) {
            System.out.println(queue.get(a));
        }

        //System.out.println(copy);System.out.println("" + car.getX() + " " + i + " " + b.currentCar);
        queue.add(copy);
    }
}

I thought there might be a problem with references, but I could not come up with any reasons why it should not be working.

edit: Here's my entire code for reference: BreadthFirstSearch.java, Board.java AND Vehicle.java

Answer 1

Your problem looks two fold:

1. You are missing the first node (or board) when you print out the list the second time.
2. You are printing the third item twice.

The solution for one: Is seen at line 94 in your BreadthFirstSearch class in the pastebin:

System.out.println(firstNode);
            LinkedList<Board> queue = new LinkedList<Board>();
            queue.addFirst(firstNode);
            Board solved = null;
            while (queue.size() != 0) {
                    Board b = queue.get(0);

                    System.out.println("!===========\ns: " + queue.size() + "\n");
                    //for (int i = 0; i < queue.size(); i++){System.out.println(queue.get(i));}
                    queue.remove(0);

You are retrieving the first item, and then you remove it. So you are missing the first item. I don't think there is any reason for you to remove that node.

The solution for problem number 2:

It looks like you are adding a node with the same information twice in the if statement between lines 110 - 133:

 if (car.getDir().equals("V")) {
     // go through every position before the current car's X
     for (int i = 0; ((i < car.getX()) && (i < (5 - car.getLen()) + 1)); i++) {
         // no car in current position? create new vehicle
         // instance
         if (isSafeVertical(b, car, i)) {
             Board copy = new Board(b.boardVehicles, b.moves, nextCar);
             copy.moveVehicle(i, car.getY(), b.currentCar);
             queue.add(copy);
         }
     }
     // go through every position after current car's x
     for (int i = car.getX() + 1; i < (5 - car.getLen()) + 1; i++) {
         // no car in current pos? create new vehicle instance.
             if (isSafeVertical(b, car, i)) {
                 Board copy = new Board(b.boardVehicles, b.moves, nextCar);
                 copy.moveVehicle(i, car.getY(), b.currentCar);
                 queue.add(copy);
             }
     }
     // move horizontal cars and add to queue

Look at how you are adding the nodes there and look at how you are adding nodes to the queue in the for statement that prints out the nodes.