Why a Word Ladder Needs a Graph Search: BFS in JavaScript

TINY and MEND differ in three letter positions. But in my game's dictionary, the shortest valid transformation takes four moves.

That extra move is a useful example of why a word ladder needs a graph search: making a valid move does not always mean getting visibly closer to the target.

I built a Word Ladder Solver as part of Word Ladder Daily, a browser-based word game. It accepts two four-letter English words and returns a shortest transformation between them.

Here is how the search works, and a few details that matter when turning the algorithm into a usable tool.

The problem

A word ladder has three rules:

• Change exactly one letter per move.
• Keep the word length unchanged.
• Every intermediate word must exist in the dictionary.

For example, the solver returns this route:

TINY → TINS → TENS → TEND → MEND

That is four moves and five words. The starting word does not count as a move.

This was also the daily puzzle for October 20, 2026.

Why “get closer every time” can fail

One tempting shortcut is to count how many letters differ from the target, then only accept moves that reduce that count.

For equal-length words, this count is the Hamming distance.

Here is what it looks like along the solution:

Word	Positions that differ from MEND
TINY	3
TINS	3
TENS	2
TEND	1
MEND	0

The first move, TINY → TINS, changes a letter without reducing the distance.

In the current dictionary, the immediate neighbors of TINY are:

TIDY — distance 4 from MEND
TINS — distance 3 from MEND
TINT — distance 3 from MEND

None improves on the starting distance of three. A rule that requires strict improvement would stop immediately, even though a solution exists.

The lesson is specific: do not discard valid moves just because they fail to reduce the number of mismatched letters.

Treat the dictionary as a graph

The graph model is straightforward:

• Each accepted word is a vertex.
• Two words share an edge if they differ at exactly one position.
• Every edge costs one move.

Finding the shortest ladder becomes finding the path with the fewest edges in an unweighted graph.

Breadth-first search fits this directly. It explores all words one move away, then all words two moves away, and so on.

When the target is reached, all shorter distances have already been explored. That is what gives BFS its shortest-path guarantee here.

Finding neighbors with wildcard buckets

The current word list contains 1700+ four-letter words.

Rather than compare every pair of words for every search, the application builds a reusable neighbor index.

For TINY, the wildcard patterns are:

*INY
T*NY
TI*Y
TIN*

Words sharing a pattern are candidates for a one-letter move. For example, TINY, TINS, and TINT all share TIN*.

The implementation groups words into these buckets, then builds an adjacency list for each word, excluding the word itself.

Neighbor lists are sorted, so repeated searches against the same dictionary return the same route when several shortest solutions exist.

The BFS search

Here is a simplified version of the search logic.

graph is a Map from each uppercase dictionary word to its array of valid neighbors. It includes words with no neighbors as empty arrays. Input trimming and case normalization happen before this function is called.

function shortestLadder(start, target, graph) {
  if (!graph.has(start) || !graph.has(target)) return null;
  const queue = [start];
  const parent = new Map([[start, null]]);

  for (let head = 0; head < queue.length; head++) {
    const word = queue[head];

    if (word === target) {
      const path = [];
      for (let node = word; node !== null; node = parent.get(node)) {
        path.push(node);
      }
      return path.reverse();
    }

    for (const next of graph.get(word) ?? []) {
      if (parent.has(next)) continue;
      parent.set(next, word);
      queue.push(next);
    }
  }
  return null;
}

A few details are worth explaining:

• The parent map also tracks visited words. A word is marked when it enters the queue, preventing cycles and duplicate work.
• Only one parent is stored per word. The complete path is reconstructed after reaching the target.
• The queue uses a moving index. There is no need to remove its first element on every iteration.
• Identical endpoints return a one-word path. That represents zero moves.
• An exhausted queue returns null. Both words can exist in the dictionary without being connected.

With the adjacency list already built, the BFS traversal takes O(V + E) time in the worst case and O(V) additional space. Building and storing the graph is a separate cost.

“Shortest” depends on the dictionary

The solver finds a shortest route within the game's word list.

That qualification is part of the result, because another dictionary can produce a different answer. Adding one intermediate word might create a shorter route; removing one might disconnect two words entirely.

The game and solver therefore share the same dictionary. A route suggested by the solver should also be playable under the game's rules.

There is also a distinction between two user-facing errors:

• An input word is not in the supported dictionary.
• Both words are supported, but no connecting route exists.

Calling both cases “invalid words” would give the user the wrong explanation.

The search runs in the browser using the bundled dictionary. It does not need a dictionary API request for each move.

Reusing the search for hints

The same search can help a player who gets stuck.

Starting from the player's current word, find a shortest remaining route and use its second word as the next step.

There is one extra constraint in the game: players cannot repeat words they have already used. The hint search therefore excludes earlier words in their path while allowing their current word as the starting point.

That makes the hint legal for the player's actual position.

What I would improve next

The search minimizes the number of moves. It does not measure how familiar the intermediate words are.

Two equally short routes can feel very different if one uses everyday vocabulary and the other includes an obscure word.

A possible next step would be to prefer familiar words among routes of the same minimum length. The current version uses sorted neighbors for deterministic results; it does not yet rank routes by word familiarity.

For a word game, that dictionary decision can matter as much as the search algorithm.

You can try the online word ladder solver with TINY → MEND, or bring your own pair of four-letter words.