Balanced

Analysis

The four strategies share the same underlying greedy placement algorithm but differ in word ordering and, in the case of Adjacency-Aware, in which placements are considered valid. This means performance differences stem from two factors: the cost of computing the ordering, and the size of the candidate set evaluated per word.

Graph-guided, Balanced, and Longest First operate exclusively on the user's word list. Their placement pass considers only perpendicular intersection candidates (positions where a new word crosses an existing word at a shared letter). Longest First skips the graph-build step entirely, making it the fastest strategy in every scenario. Graph-guided and Balanced are similar in cost because they both compute the compatibility graph; Balanced adds a minor constant factor for its hybrid seed selection.

Adjacency-Aware adds two sources of overhead. First, each word's candidate set is larger because parallel placements (same direction, offset by one row or column) are enumerated alongside perpendicular intersections. For a word of length L placed beside an existing word of length P, this adds up to 2 × (L + P - 1) additional candidates per pair. Second, every candidate undergoes perpendicular-run validation against the dictionary, which requires walking the grid in the perpendicular direction at each cell. Phase 2 (gap filling) adds a third cost: scanning for 2-letter fragments and searching dictionary buckets for valid extensions.

The practical impact scales with word count. On a 9-word themed list, the adjacency strategies run in roughly 126-129ms versus 1.2ms for Longest First (approximately 100x slower). On 156 words, the gap narrows to roughly 65x (5.1-5.2s versus 79ms). The overhead comes from dictionary validation of perpendicular runs, parallel candidate enumeration, and gap filling.

An important caveat applies when comparing intersection counts across strategy types. The adjacency strategies' reported intersections include crossings involving dictionary fill words. For the mixed-large scenario, Adjacency-Aware places 228 total words (156 user + 72 fill) and reports 312 intersections, while Densest Crossings places 153 user words and reports 157 intersections. Some portion of the intersection difference is attributable to the additional fill words, not to more efficient placement of the original word list.

The 2-letter fragment count reveals an inherent tradeoff of parallel placement. Every pair of words placed side-by-side creates perpendicular 2-letter runs that must either be extended into dictionary words or left as fragments. Inline gap filling (used by both adjacency strategies) mitigates this by resolving gaps immediately after each parallel placement, while surrounding constraints are still loose. Parallel-Seeded reduces fragments by roughly 43% compared to deferred filling on large word lists, producing 24 fragments versus 35 for base Adjacency-Aware on the mixed-large scenario. The remaining fragments are structurally unfillable due to constraints accumulated during grid construction.

The compactness metric (grid area divided by placed words) also requires careful interpretation. Adjacency-Aware tends to produce grids with lower compactness values, which suggests denser packing. However, the fill words extend existing perpendicular runs rather than expanding the grid boundary, so they reduce compactness partly by inflating the denominator without proportionally increasing the numerator. Among the user-word-only strategies, Longest First tends to produce the most compact grids, likely because long anchor words create a tighter bounding box relative to the words they accommodate.

Each strategy was run 3 times with 16 randomized attempts per run. Adjacency-aware loads the full crossword dictionary (~42K words, filtered to 3-8 letters with score >= 60) for perpendicular validation and gap filling; other strategies use only the scenario's word list. Note that adjacency-aware's "placed" count includes dictionary fill words from Phase 2, so its intersection counts are not directly comparable to other strategies, which only place words from the input list.