Your problem looks two fold:
- You are missing the first node (or board) when you print out the list the second time.
- 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.