crossword-generator-x

A crossword layout generator that combines two complementary algorithms — greedy scored placement and recursive backtracking — to maximize the number of words placed in a valid crossword grid.

Install

npm install crossword-generator-x

Why?

Two popular crossword generators exist on npm:

• crossword-layout-generator — Fast greedy placement with smart scoring. Works most of the time, but once a word is placed it's never reconsidered. Early placements can block later words.
• cwg — Recursive backtracking. Can undo bad placements, but it's all-or-nothing (every word must fit or it fails entirely) and slow on large inputs.

They literally cover each other's blind spots. This project merges them into one.

How It Works

Each generation attempt runs a 2-phase pipeline, and the whole thing is wrapped in a retry loop:

Phase 1: Greedy Scored Placement

Every unplaced word is evaluated at every valid grid position in both orientations. The best (word, position) pair is selected using a weighted score:

| Weight | Factor | What it does | |--------|--------|-------------| | 70% | Connections | Ratio of letter intersections to word length. More crossings = better. | | 15% | Centrality | Manhattan distance from grid center. Keeps the puzzle compact. | | 10% | Orientation balance | Favors whichever direction (across/down) is underrepresented. | | 5% | Word length | Slight bonus for longer words. |

This places ~80-90% of words quickly. Words that can't be placed are passed to Phase 2.

Phase 2: Backtracking

Remaining words are placed using recursive backtracking:

1. Find all valid positions for the next unplaced word
2. Shuffle them (randomness enables different solutions across retries)
3. Try each one — if placing it makes a later word impossible, undo and try the next position
4. If no position works for a word, backtrack further up the chain

This catches cases where the greedy pass painted itself into a corner.

Retry Loop

The 2-phase pipeline runs multiple times (default: 50 attempts, 10s timeout) with shuffled word order each attempt. Different input orders lead to different greedy decisions, producing different layouts. The best result (fewest unplaced words) is returned. If all words are placed, it stops early.

Placement Rules

A word placement is valid when:

• No letter conflicts (each cell is empty or already contains the same letter)
• No parallel adjacency (empty cells being filled can't neighbor existing letters perpendicular to the word — prevents side-by-side words without intersection)
• No consecutive shared cells (two letters in a row can't both overlap existing words)
• Bookend cells before/after the word must be empty (no abutting)
• At least one cell must be empty (can't fully overlap an existing word)
• During backtracking: must intersect at least one existing word (keeps the puzzle connected)

After placement, any word with zero intersections is removed to prevent disconnected islands.

Usage

import { generateLayout } from "crossword-generator-x";

const result = generateLayout([
  { answer: "HELLO", clue: "A greeting" },
  { answer: "WORLD", clue: "The planet" },
  { answer: "HOWDY", clue: "Casual greeting" },
  { answer: "LOVER", clue: "Romantic partner" },
  { answer: "DWELL", clue: "To reside" },
]);

Also works with CommonJS:

const { generateLayout } = require("crossword-generator-x");

Options

generateLayout(words, {
  maxAttempts: 50,                  // retry attempts with shuffled word order
  timeoutMs: 10000,                 // max total time in ms
  weights: [0.7, 0.15, 0.1, 0.05], // [connections, centrality, balance, length]
  gridFactor: 3,                    // grid size = longest word * factor
});

Output

{
  table: [['H','E','L','L','O'], ...],  // 2D character grid ("-" = empty)
  result: [                              // word objects
    {
      answer: "HELLO",
      clue: "A greeting",
      startx: 1,            // 1-indexed column
      starty: 3,            // 1-indexed row
      orientation: "across", // "across", "down", or "none" (unplaced)
      position: 1,           // clue number
    },
    // ...
  ],
  rows: 6,
  cols: 8,
  table_string: "..WORLD\n..D...O...",  // flat string representation
  unplaced: 0,                           // count of words that couldn't be placed
}

Types

All types are exported:

import type {
  WordInput,
  WordResult,
  LayoutOptions,
  LayoutResult,
  Orientation,
} from "crossword-generator-x";

License

MIT