Framework

int bfs(State start, Predicate isGoal, Function> neighbors) {
  Map dist = new HashMap<>();
  Deque q = new ArrayDeque<>();
  q.offer(start); dist.put(start, 0);
  while (!q.isEmpty()) {
    State u = q.poll();
    if (isGoal.test(u)) return dist.get(u);
    for (State v : neighbors.apply(u))
      if (!dist.containsKey(v)) {
        dist.put(v, dist.get(u) + 1);
        q.offer(v);
      }
  }
  return -1;
}
Advertisement

Puzzles

15-puzzle: state = 4x4 grid, neighbors = swap blank with adjacent. Word ladder: state = word, neighbors = 1-letter change.

Advertisement

State hashing

Encode state compactly for hash map. Bit packing for grids. Canonical forms for symmetries.

Memory concern

Visited set can be huge. IDA* or bidirectional BFS reduces memory.