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:

Words are sorted longest-first (harder to place, so they go early)
The first word is placed horizontally at the center of the grid
For each subsequent word, the algorithm finds all positions where it shares a letter with an already-placed word (intersection)
Candidates are scored by number of intersections and proximity to center
The algorithm recursively tries each candidate, backtracking if it leads to a dead end
If the first ordering fails, it retries with shuffled orderings (up to 10 attempts)
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)

Longest Word	Grid Size
3-5 letters	9x9
6-8 letters	11x11
9-11 letters	13x13
12+ letters	15x15

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.

ryangaudet / crossword-grid-builder

Maintainers

Package info

Statistics

Security