Densest Crossings

This strategy treats your word list as a graph problem. Each word is a node, and two words are connected by an edge if they share at least one letter, meaning they could potentially cross in the grid.

The placement order is then derived from this graph: start with the most connected word (the one that could cross the most other words), and at each step add the unplaced word that has the most connections to words already on the grid.

By clustering interconnected words together in the placement order, the greedy placer is much more likely to find positions where a new word crosses multiple existing words simultaneously, producing denser layouts than naive ordering.

How It Works

1. 1

   Build the compatibility graph

   For every pair of words (A, B), count how many distinct letter positions could line up if they crossed. If they share at least one letter, add an edge in the graph weighted by the number of crossing options. This is a one-time O(W² × L²) preprocessing step.

2. 2

   Pick the seed word

   Find the word with the highest degree (most edges to other words). On the first attempt, ties are broken by word length. On subsequent attempts, the seed is randomized among the top-third highest-degree nodes to produce diverse layouts.

3. 3

   Iteratively add the most connected unplaced word

   At each step, score every unplaced word by how many edges it has to already-placed words. Pick the highest scorer (with shared-letter count and small randomness as tiebreakers). This naturally builds tight clusters of compatible words.

4. 4

   Hand the ordering to the greedy placer

   Once the order is determined, the standard greedy placer takes over: place each word at the position that maximizes intersections with existing words on the grid. The graph-guided ordering ensures these greedy choices produce denser results than longest-first or random ordering.

Pseudocode

function graphGuidedOrder(words, graph):
    picked = {}
    order = []

    // Step 1: pick seed (highest degree)
    seed = argmax(words, w => degree(w in graph))
    order.append(seed)
    picked.add(seed)

    // Step 2: greedily add most-connected unplaced word
    while picked.size < words.size:
        best = null
        bestScore = -1
        for w in words \ picked:
            edgesToPicked = count(edge in graph[w] where edge.other in picked)
            score = edgesToPicked × 10000 + sharedLetterTotal(w) × 100
            if score > bestScore:
                best = w
                bestScore = score
        order.append(best)
        picked.add(best)

    return order

Complexity

Graph build: O(W² × L²) where W = word count, L = average word length. Ordering: O(W² × E) where E = average edges per word. For typical lists (10–50 words), this is microseconds.

★ Best across all four strategies on this scenario. Reproducible via scripts/benchmark-strategies.ts.

Metric Definitions

Each benchmark run executes 16 randomized attempts of the strategy and returns up to 4 distinct layouts, sorted by quality. This process is repeated 3 times to reduce variance. The metrics below describe how each column is derived from those runs.

Best ×

The highest intersection count from the top-ranked layout across 3 independent runs. An intersection is a grid cell shared by two words (one across, one down). Higher is better.

Avg ×

The mean intersection count across all returned layouts (up to 4 per run), averaged over 3 runs. This includes second- through fourth-best layouts, so it reflects consistency rather than peak performance.

Placed

The most words placed on the grid in any top-ranked layout. For Adjacency-Aware, this includes dictionary fill words from Phase 2, so it can exceed the input word count. Shown as placed/input.

Compactness

Grid bounding-box area (rows times columns) divided by the number of placed words. Lower values indicate denser packing. Note that this measures the full bounding box, which includes empty cells between words. Adjacency-Aware's denominator is inflated by fill words.

2-Letter Frags

The number of 2-letter contiguous letter runs in the best grid that are not covered by any placed word in that direction. These are perpendicular fragments left behind by parallel placements that Phase 2 could not extend into complete dictionary words. Only applicable to adjacency strategies; always 0 for other strategies since they never place words in parallel.

Fill Words

The number of dictionary words added in Phase 2 to extend 2-letter gaps into complete words. These are not from the user's word list. Capped at max(3, 75% of user word count). Only applicable to adjacency strategies.

Time

Wall-clock time for one run (16 randomized attempts), averaged across 3 runs. Measured in single-threaded JavaScript without Web Workers. Includes ordering, candidate enumeration, validation, and (for Adjacency-Aware) Phase 2 gap filling.

When to Use This

• •Your word list has many shared letters (vowels, common consonants)
• •You want maximum visual density in the resulting crossword
• •You're building a themed puzzle where related words tend to share letters

Other Strategies