This project applies parallel execution and work-avoidance techniques to the problem of solving word search puzzles. While the problem itself is simple in surface complexity, naive implementations waste computation by performing string comparisons that are guaranteed to fail. The design focuses on reducing unnecessary work and structuring data in a way that makes concurrency both practical and meaningful.

Parallelism was not a requirement of the problem. It was introduced intentionally as a way to explore concurrency, data partitioning, and result aggregation in a domain where correctness could be easily verified.

Implementation and Design

The solver loads a puzzle definition from a structured input file containing puzzle dimensions, grid data, and a list of target words. Once loaded, the puzzle is decomposed into directional search areas by scanning horizontally, vertically, and diagonally. Backward searches are handled implicitly during comparison, eliminating the need to generate redundant data and reducing memory overhead.

All directional scans are implemented through a single parameterized scanning routine. The scanner determines valid edge start positions, advances correctly across puzzle boundaries, and detects termination conditions. This abstraction significantly reduced duplication and made diagonal traversal easier to reason about and debug.

Search areas are grouped by length before comparison. Each search word is only compared against pools of search areas of equal or greater length, preventing comparisons that cannot succeed by construction. Each search area retains its starting coordinates so that successful matches can be translated directly into puzzle locations.

Parallel execution is introduced during the comparison phase. Threads are spawned to compare search words against appropriate pools of search areas, and results are returned using futures and promises. To support this, search strings are paired with positional metadata in a dedicated data structure, allowing threads to return both match results and coordinates in a single operation.

Thread creation and scheduling were intentionally kept simple. The goal was to explore concurrency mechanics, ownership transfer, and result aggregation rather than exhaustively optimize scheduling behavior.

Objectives

The primary objectives were to load and solve arbitrary word search puzzles, reduce unnecessary string comparisons through data shaping, and apply parallel execution in a controlled and verifiable way. An additional goal was to gain practical experience with futures, promises, and move semantics in a concurrent context.

Challenges and Outcomes

One challenge involved determining how to return positional information from parallel execution. Initial implementations focused solely on string matching and deferred location reporting, which later required refactoring to associate search areas with coordinate data.

Another challenge was mastering futures and promises for result retrieval. While thread creation was straightforward, correctly transferring ownership of promises required a deeper understanding of move semantics to ensure results could be retrieved reliably.

Despite these challenges, the system achieved correct and efficient behavior, producing accurate word locations while avoiding unnecessary comparisons.

Results

The final implementation reliably solves word search puzzles while avoiding unnecessary computation by constraining comparisons by direction and length. In practice, both the sequential and parallel implementations completed nearly instantaneously for typical inputs.

An initial parallel implementation performed worse than the sequential version, as thread creation and coordination overhead dominated the workload. Achieving comparable performance required revisiting how the problem was decomposed and increasing the granularity of work assigned to each thread. Once adjusted, the parallel version approached sequential performance but did not meaningfully exceed it.

This outcome reinforced a practical lesson: parallelism is sensitive to problem decomposition, and without sufficient work per thread, overhead can outweigh any theoretical gains. The project ultimately demonstrated when concurrency is inappropriate as much as how it can be implemented correctly.