Fast Heuristic Detection of Offensive Words in Wordwheel Puzzles

Anand D. Blum, R. Mitchell ParryAAAI 2022 · DOI

Introduction

Wordwheel puzzles, such as the popular New York Times Spelling Bee, are a staple of modern digital and print media. These puzzles challenge players to form words using a central "hub" letter and a surrounding ring of letters. While seemingly benign, these puzzles face a significant social challenge: the "slur problem." Because the outer letters can be rearranged or permuted, an innocent set of letters might inadvertently display an offensive term in a highly visible way, such as spelled out clockwise around the rim.

A typical Wordwheel puzzle layout and rules.

Manually curating every possible permutation of letters to avoid offensive content is computationally expensive and difficult to scale, especially for real-time digital versions that allow users to shuffle the board. Traditional methods, like Depth-First Search (DFS), are accurate but can be slow when processing thousands of concurrent requests. This paper, presented at AAAI-22, introduces a high-performance heuristic designed to detect these "obvious" offensive words using efficient bitwise operations.

Methodology: Bigram-based Bitmasking

The researchers developed a bigram-based bitmask heuristic that shifts the problem from graph traversal to simple bitwise logic. Instead of searching for an entire word, the algorithm verifies if the necessary pairs of adjacent letters (bigrams) exist in the current puzzle configuration.

The Encoding Process

  1. Preprocessing: Each unique letter in the puzzle's outer ring is mapped to an integer from 0 to 7.
  2. Taboo Mask Generation: For every word in a predefined "taboo list," a 64-bit integer (bitmask) is created. Each bit represents a specific bigram $(i, j)$. If a taboo word contains the bigram $(i, j)$, the bit at position $8i + j$ is set to 1.
  3. Puzzle Mask Generation: A similar 64-bit mask is generated for the current arrangement of letters on the board, representing all visible adjacent letter pairs.

The Heuristic Check

The core detection is performed using a single bitwise-AND operation: (PuzzleMask & TabooMask) == TabooMask If this condition is met, all bigrams required to form the taboo word are present and adjacent in the current layout. This approach is mathematically guaranteed to have a zero false-negative rate for contiguous paths, ensuring that no "obvious" offensive word goes undetected. The paper defines a word as "obvious" if it follows a simple path of contiguous, non-repeated letters, targeting the most jarring accidental slurs that appear directly in the player's line of sight.

Evaluation and Results

The system was evaluated using the Linux Operating System Word List (5,286 nine-letter words) and Google’s Banned Word List (327 words). The primary goals were speed and safety (minimizing false negatives).

Confusion matrix showing the heuristic's performance metrics, including a 100% True Positive Rate.

The results demonstrate that the heuristic is exceptionally effective for its intended purpose. It achieved a 100% True Positive Rate (TPR), meaning it never failed to flag an offensive word that was present. The False Positive Rate (FPR) averaged 1.25%. Notably, in puzzles without repeated letters—common in many professional formats—the FPR drops to 0%, providing perfect accuracy.

The "Repeated Letter Quirk" explains the small margin of false positives in general datasets. In puzzles where letters are repeated, the bitmask might indicate that all necessary bigrams for a taboo word are present, even if they do not form a single continuous string. However, for NYT-style puzzles which use 7 unique letters, this is not an issue.

In terms of performance, the bitwise approach significantly outperforms standard DFS when checking against a large dictionary of taboo words. By reducing the computational burden to a series of bitwise comparisons, the system is well-suited for high-traffic production environments.

Conclusion

This research provides a robust engineering solution for maintaining family-friendly environments in digital word games. By prioritizing a zero false-negative rate and leveraging the speed of bitwise operations, the authors have created a tool that is both "fast enough for real-time" and "safe enough for a classroom." Future applications could extend this logic to automated game design, ensuring puzzles are balanced and do not inadvertently reveal common words too easily.

Summary updated

BibTeX
@inproceedings{blum2022fast,
  author = {Anand D. Blum and R. Mitchell Parry},
  title = {{Fast Heuristic Detection of Offensive Words in Wordwheel Puzzles}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21549},
}

Loading related content...

Figure