Word Ladder Solver

This project was super fun. I already enjoyed playing Word Ladder, so turning it into a search problem felt less like completing an assignment and more like learning how a game I liked worked underneath.

Because it was an individual project, I owned every decision from the graph representation and search loop to the interface and performance measurements. Having complete control meant I also needed complete knowledge of the implementation, which made it a valuable learning experience.

A* became my favorite of the three algorithms. Before learning informed search, Uniform Cost Search seemed like the natural solution: explore words by their distance from the start until the target appears.

A* considers both how far the search has already traveled and how close the current word appears to the goal. It keeps the optimal-result guarantee while using additional information to choose which possibilities deserve attention first. Once I understood it, A* felt like a formal version of how a person might approach the puzzle.

I chose Hamming distance as the heuristic. It counts how many letter positions differ between the current word and the target. If k positions differ, at least k moves are needed because one legal move changes only one letter.

That makes the heuristic admissible: it never overestimates the true shortest remaining cost. It is also consistent because moving to a neighboring word can change the Hamming distance by at most one. The heuristic gives A* direction without allowing it to become overconfident.

Uniform Cost Search found an optimal ladder but often expanded many words. Greedy Best-First Search expanded dramatically fewer words but could return a longer path. A* combined the traveled cost and heuristic, retaining optimality while reducing unnecessary exploration.

For atom to mine, UCS expanded 3,035 nodes and returned a 10-word ladder. Greedy expanded only 16 nodes but returned an 11-word ladder. A* returned the optimal 10-word result after expanding 139 nodes. I expected the tradeoff, but seeing it inside my own implementation made it concrete.

The application used more than 80,000 words. Generating every possible neighbor during every search would repeat the same work, so I precomputed the adjacency graph.

For each word, the program tested possible one-letter mutations and stored valid dictionary connections. The preparation happened once, allowing every interactive search to retrieve neighbors directly.

The algorithms were challenging, but enjoyable enough that they did not feel frustrating. The interface was harder because I had not used the desktop UI stack before.

The repository eventually used Java Swing for the GUI alongside a command-line version. The solver remained independent from both interfaces, allowing the same search implementation to support either one.

The most satisfying result was solving atlases to cabaret, a widely cited difficult Word Ladder pair. Watching my application produce a valid path felt like proof that the solver worked beyond small examples.

It brought together a large graph, a long path, a useful heuristic, and an implementation capable of reconstructing the complete solution.

The biggest lesson was that technology choices are rarely absolute. UCS was optimal but explored heavily. Greedy could be extremely fast but sacrificed the shortest-path guarantee. A* balanced both concerns, but depended on a useful and valid heuristic.

The right choice depends on the use case. This project taught me to stop asking which algorithm is universally best and start asking which tradeoff fits the problem.

I would enjoy turning the solver into a web game. A browser version could let people play, ask the algorithms for help, and compare all three strategies side by side.

It could visualize the frontier, animate the discovered ladder, and show how many words each method explored, making the same algorithmic lesson easier for other people to experience.