You’ve definitely seen one of these before:

C A N T O R
G A U S S .
E U L E R .
A B E L . .
. . . . . .
. . . . . .

A grid of letters hiding several words — horizontally, vertically, sometimes diagonally. Finding them is the game, but creating the puzzle is the interesting engineering problem: given a list of words, how do you fit them all into a grid?

This is harder than it looks. Words can go diagonally, they can go backwards, and two words might intersect at the same cell — where the letters must match. Brute-forcing every possible placement is too expensive and easy to get wrong.

This article introduces an elegant approach: turn “puzzle construction” into a coloring game, then let Dancing Links solve it automatically. Along the way, we’ll expose a detail that’s surprisingly easy to get wrong — and a little trick Knuth uses to fix it.

Let’s Define the Problem

Given 4 words — ABEL, CANTOR, GAUSS, EULER — and a 6x6 grid, the rules are:

• Each word must be placed exactly once
• Words can go horizontally, vertically, or diagonally (8 directions)
• If two words intersect at a cell, that cell’s letter must be the same for both

Question: how many valid placements are there?

The answer is 244,792.

By hand? Impossible. Brute force? Too slow. The method in this article computes it in seconds.

Turning “Word Placement” into “Coloring”

The key insight: we can reformulate this problem as a coloring problem.

Imagine each cell as a blank square that can be painted with a letter’s color. The rule is simple:

A cell can be colored multiple times, but every coloring must use the same color.

Each “place a word at some position in some direction” is a coloring option — it paints each cell it passes through with the corresponding letter.

For example, the option “place ABEL starting at (0,0) going east” paints:

• Cell (0,0) with A
• Cell (0,1) with B
• Cell (0,2) with E
• Cell (0,3) with L

If another option also passes through cell (0,3), it must also paint it L, otherwise there’s a conflict.

This “repeatable but must be the same color” constraint is exactly the “color item” extension that Knuth introduced in TAOCP 4B. In short: a color item can be covered multiple times, as long as every covering carries the same color (here, the same letter). The previous post covered the basics; this article tackles a pitfall that almost everyone falls into when using color items.

Two Words Sharing a Cell — Looks Right, Actually Wrong

Let’s look at the smallest counterexample. Place ABEL and LAND in a 4x4 grid. They can intersect at the letter L:

A B E L
. . . A
. . . N
. . . D

ABEL goes across row 0, LAND goes down from cell (0,3). Both words pass through cell (0,3), both with the letter L — valid!

When we express this with color items, here’s roughly what the algorithm does during search:

1. Choose the option “ABEL across row 0”
2. Color cell (0,3) with L
3. Purify: scan all other candidates in cell (0,3)’s column, remove those that want to color (0,3) a different color
4. Next, choose “LAND going south from (0,3)”

The problem comes after step 4: the LAND-going-south option also passes through cell (0,3), so it also needs to “purify” cell (0,3) — scanning the column again, removing candidates with the wrong color again.

But some candidates were already removed in step 3!

What happens when you remove something twice?

Imagine there’s a candidate option X in cell (0,3)’s column with color D (not L). Step 3 removes it and decrements the column’s “remaining available candidates” count by 1. Step 4 removes it again, decrementing the count by another 1.

During backtracking, the two removals are only undone once, so the counter gets corrupted. Some columns still have available options, but the counter says “none left” — the algorithm incorrectly thinks it’s hit a dead end or takes a wrong turn, ultimately producing wrong answers.

If we restrict to horizontal and vertical directions only (no diagonals) and require that the two words share at least one cell, the correct answer is 16 solutions. But the buggy version reports 28. The extra 12 are all wrong, but the program won’t raise an error — it silently gives you bogus answers.

Running the buggy version on the ABEL+LAND puzzle confirms this: the program reports 28 solutions instead of the correct 16.

The Sticker Fix

The root cause of this bug: the first purification leaves no trace, so the second purification thinks it’s the first one to operate.

Knuth’s fix is remarkably simple: make the first purification leave a sticker.

Rule: When a purify operation scans a column, candidates with the same color aren’t just skipped — they get tagged as “already processed” (called COMMITTED in the book). When a hide operation encounters a node with the “already processed” tag, it simply skips it and does nothing.

The effect:

• The first purification (from ABEL’s option) tags a candidate in cell (0,3) with color L
• The second purification (from LAND’s option) scans to this candidate, sees the tag, skips it, no duplicate operation

During backtracking, the reverse scan peels off the tags and restores the original colors — everything back to normal.

There’s a subtle elegance to this sticker mechanism: the currently selected option’s own nodes never get tagged. Because before purification begins, the selected option has already been “extracted” from the column link (for other operations), so the purification scan can’t find it. This way, the node’s color always remains the original value during backtracking, which is how the algorithm correctly determines “which restore operation to call.”

The Code

Here’s the key code with the sticker mechanism (full implementation at dlx_colors.py):

_COMMITTED = object()   # Sticker: already processed by outer purification

def _hide(row_node):
    """When hiding a row, skip nodes with stickers"""
    j = row_node.R
    while j is not row_node:
        if j.color is not _COMMITTED:   # Has a sticker? Skip
            j.D.U = j.U
            j.U.D = j.D
            j.C.S -= 1
        j = j.R

def _purify(self, node):
    """Purify: tag same-color nodes, remove different-color ones"""
    col, color = node.C, node.color
    i = col.D
    while i is not col:
        if i.color == color:
            i.color = _COMMITTED    # Same color: apply sticker
        else:
            self._hide(i)           # Different color: remove
        i = i.D

def _unpurify(self, node):
    """Backtrack: peel off stickers or restore removed rows, in reverse"""
    col, color = node.C, node.color
    i = col.U                       # Note: reverse order
    while i is not col:
        if i.color is _COMMITTED:
            i.color = color         # Peel sticker, restore original color
        else:
            self._unhide(i)         # Restore removed row
        i = i.U

Full Modeling of the Word Search Puzzle

With this mechanism in place, translating the word search puzzle into algorithm input is straightforward:

Each “placement” (word + position + direction) corresponds to a row, covering:

• The primary column for that word (meaning “this word has been placed”)
• The color column for each cell it passes through, with color = the corresponding letter

def create_word_search(rows, cols, words, allow_diagonal=True):
    W = len(words)
    num_primary = W                  # First W columns are primary (words)
    num_items   = W + rows * cols    # Remaining: one column per cell (color)

    options, labels = [], []

    for w_idx, word in enumerate(words):
        for dir_name, (dr, dc) in DIRECTIONS.items():
            for sr in range(rows):
                for sc in range(cols):
                    # Bounds check
                    er = sr + dr * (len(word) - 1)
                    ec = sc + dc * (len(word) - 1)
                    if not (0 <= er < rows and 0 <= ec < cols):
                        continue
                    # Build this row: primary item + color item per letter
                    option = [(w_idx, None)]
                    for k, ch in enumerate(word):
                        r, c = sr + dr*k, sc + dc*k
                        option.append((W + r*cols + c, ch))
                    options.append(option)
                    labels.append((w_idx, sr, sc, dir_name))

    dlx = DLX_C(num_primary, num_items, options)
    solutions = []
    for sol in dlx.solve():
        placement = [(words[labels[i][0]], *labels[i][1:]) for i in sol]
        solutions.append(placement)
    return solutions

Let’s run it:

words = ["ABEL", "CANTOR", "GAUSS", "EULER"]
solutions = create_word_search(6, 6, words)
print(len(solutions))   # → 244792

The first solution (all four words neatly in separate rows):

CANTOR
GAUSS.
EULER.
ABEL..
......
......

More interesting solutions involve diagonal placements and letter crossings, all handled automatically by the algorithm — the code needs zero special-casing for these situations.

Word Rectangles: Solving Another Puzzle Along the Way

Same framework, different constraints, different puzzle — word rectangles: horizontal words fill every row, vertical words fill every column, and intersecting cells must share the same letter.

C A T
D O G
E E L

Across: CAT, DOG, EEL; Down: CDE, AOE, TGL.

The modeling is entirely analogous: rows and columns are each a primary item, cells are color items. The key difference is that primary items change from “each word” to “each row and each column” — each row and column gets a primary item indicating it must be filled with exactly one valid word. Change a few lines of code and you’re done — the underlying algorithm doesn’t need to change at all.

Stepping Back

Let’s review what we did:

1. Described “word search puzzle” as “each word must be placed exactly once, each cell’s letter must be consistent”
2. Translated “letter consistency” into “same color allows multiple coverings”
3. Discovered the naive implementation has a double-operation bug
4. Fixed it with a sticker (the COMMITTED tag)

The most interesting part of the whole process: we never wrote any “how to solve the puzzle” logic. We only described “what makes a valid puzzle,” and the algorithm found all the answers on its own.

This is the most compelling quality of this class of search algorithms: describe the constraints clearly, and solving happens automatically. Creating puzzles and solving puzzles use the exact same framework.

Want to Try It Yourself?

Full code is at dlx_colors.py and word_search.py — just clone and run.

A few things to explore:

• Try different words: Plug in your own name or favorite words and see how many ways they can be hidden
• Change the grid size: Same words, but how different are the solution counts for 6x6 vs 8x8?
• Add a constraint: What if every word must intersect with at least one other word? How would you modify the model?

Feel free to share your findings in the comments.