Решатель Rush Hour работает в бесконечном цикле любая нетривиальная головоломка

Question

Итак, я пишу часовую чашку Rush Hour на Java, которая предназначена для решения конфигураций here. Однако даже самая простая головоломка с этой страницы приводит к тому, что решатель работает бесконечно и в конечном итоге исчерпывает память. Я использую первый поиск по ширине, чтобы работать на всех возможных ходах, возникающих из каждого состояния платы (используя HashSet для обеспечения того, чтобы я не повторялся) и сопоставлял каждое состояние с ходом, который получил его, чтобы я мог отступить через них позже.

Дело в том, что я попробовал это с более загадочными головоломками, которые я придумал сам, и он может их решить (хотя и медленно).

Есть ли что-то откровенно неправильное в отношении того, как я приближаюсь к этой проблеме? Я могу вынести некоторый код из соответствующих классов, если это необходимо, но я проверил их довольно тщательно, и я уверен, что проблема находится где-то в приведенном ниже коде. Моя кишка говорит, что это как-то связано с HashSet и поэтому я не повторяюсь (поскольку размер очереди достигает 100 тысяч).

Любые предложения?

// Start at the original configuration 
    queue.add(originalBoard); 

    // We add this to our map, but getting here did not require a move, so we use 
    // a dummy move as a placeholder move 
    previous.put(originalBoard, new Move(-1, -1, "up")); 

    // Breadth first search through all possible configurations 
    while(!queue.isEmpty()) { 
     // Dequeue next board and make sure it is unique 
     Board currentBoard = queue.poll(); 
     if (currentBoard == null)   continue; 
     if (seen.contains(currentBoard)) continue; 
     seen.add(currentBoard); 

     // Check if we've won 
     if (currentBoard.hasWon()) { 
      System.out.println("We won!"); 
      currentBoard.renderBoard(); 
      return solved(currentBoard); 
     } 

     // Get a list of all possible moves for the current board state 
     ArrayList<Move> possibleMoves = currentBoard.allPossibleMoves(); 

     // Check if one of these moves is the winning move 
     for (Move move : possibleMoves) { 
      Board newBoard = move.execute(currentBoard); 

      // We don't need to enqueue boards we've already seen 
      if (seen.contains(newBoard)) continue; 
      queue.add(newBoard); 

      // Map this board to the move that got it there 
      previous.put(newBoard, move); 
     } 
    } 

В соответствии с просьбой, вот мои инициализацый о HashSet (они переменные уровня класса):

private static HashSet<Board> seen = new HashSet<>(); 

И мои Board.equals() метод:

@Override 
public boolean equals (Object b) { 
    Board otherBoard = (Board) b; 
    boolean equal = false; 
    if (this.M == otherBoard.getM() && this.N == otherBoard.getN()) { 
     equal = true; 

     // Each board has an ArrayList of Car objects, and boards are only 
     // considered equal if they contain the exact same cars 
     for (Car car : this.cars) { 
      if (otherBoard.getCar(car.getPosition()) == null) { 
       equal = false; 
      } 
     } 
    } 
    System.out.println(equal); 
    return equal; 
} 

Answer 1

You должен реализовать Board.hashCode(), чтобы переопределить версию по умолчанию Object таким образом, чтобы на каждый контракт равные Board объекты имели одинаковый хеш-код. Если вы этого не сделаете, то ваш комплект seen ничего не сделает для вас.

В другом случае я подозреваю, что способ проверки автомобилей плат не совсем корректен. Если он работает так, как я думаю, что он делает, он будет рассматривать эти две доски, чтобы быть равными: . = пустое пространство * = часть автомобиля

...... 
.**.*. 
....*. 
.*.... 
.*.**. 
...... 

...... 
.*..** 
.*.... 
...... 
.**.*. 
....*.