README

A PHP backtracking algorithm that builds crossword puzzle grids from word lists. Give it words, get back a valid crossword layout.

See it in action at CodeXword — crossword puzzles for people who code.

How It Works

The algorithm uses recursive backtracking with scoring to find optimal word placements:

1. Words are sorted longest-first (harder to place, so they go early)
2. The first word is placed horizontally at the center of the grid
3. For each subsequent word, the algorithm finds all positions where it shares a letter with an already-placed word (intersection)
4. Candidates are scored by number of intersections and proximity to center
5. The algorithm recursively tries each candidate, backtracking if it leads to a dead end
6. If the first ordering fails, it retries with shuffled orderings (up to 10 attempts)
7. A configurable timeout prevents infinite loops on impossible layouts

Installation

composer require ryangaudet/crossword-grid-builder

Usage

Basic

use RyanGaudet\CrosswordGridBuilder\GridBuilder;

$builder = new GridBuilder();

$words = ['FUNCTION', 'CLASS', 'RETURN', 'WHILE', 'ARRAY', 'STRUCT', 'ENUM', 'GUARD'];
$result = $builder->build($words, 11); // 11x11 grid

if ($result) {
    // $result['grid'] — 2D array of characters ('#' = empty, 'A'-'Z' = letter)
    // $result['placements'] — array of placed words with positions

    foreach ($result['placements'] as $placement) {
        echo "{$placement['word']} at [{$placement['row']}][{$placement['col']}] {$placement['direction']}\n";
    }

    // Print the grid
    echo $builder->toString($result['grid']);
}

Output:

 . . . . . R . S . . .
 . W H I L E . W . . .
 . . . . . T . I . . .
 . . S T R U C T . . .
 . . . U . R . C . . .
 . . . P . N . H . . .
 . . . L . . . . . . .
 . . . E N U M . . . .
 . . . . . . . . . . .

Auto-sized Grid

Let the library calculate the optimal grid size based on your longest word:

$result = $builder->buildAuto($words);

echo "Grid size: {$result['gridSize']}x{$result['gridSize']}\n";
echo "Words placed: " . count($result['placements']) . "/" . count($words) . "\n";

Configuration

// Custom timeout (default 5 seconds) and minimum word count (default 6)
$builder = new GridBuilder(
    timeoutSeconds: 3.0,
    minWords: 4,
);

Grid Sizing

The GridSizer utility calculates grid dimensions based on the longest word:

use RyanGaudet\CrosswordGridBuilder\GridSizer;

$size = GridSizer::fromWords(['FUNCTION', 'CLASS', 'RETURN']);
// Returns 11 (FUNCTION is 8 chars → 11x11 grid)

Placement Data

Each entry in $result['placements'] contains:

[
    'word' => 'FUNCTION',       // The placed word (uppercase)
    'row' => 3,                 // Starting row (0-indexed)
    'col' => 2,                 // Starting column (0-indexed)
    'direction' => 'across',    // 'across' or 'down'
]

Algorithm Details

The placement scoring considers:

• Intersections (50 pts each) — more shared letters = more connected grid
• Center proximity (up to 20 pts) — words closer to center look better

Validation rules per cell:

• A cell can only contain one letter (intersections must match)
• No parallel adjacency (prevents unintended word formation)
• No run-on (empty cell or edge required before and after each word)

The algorithm guarantees:

• All placed words are fully connected (share at least one intersection)
• No cell conflicts
• Minimum word count met (configurable, default 6)
• Completes within the timeout (configurable, default 5s)

Requirements

• PHP 8.1+

Testing

composer install
composer test

License

MIT License. See LICENSE.

About

This algorithm powers CodeXword — a crossword puzzle platform where every puzzle is built around programming terminology. 9 languages, 72 themes, from Beginner to Advanced.

Built by Ryan Gaudet.