The idea of this algorithm is that we do one "step" in the trie over many many boards and many many current states. Lets pretend we only have one board:

Terminology:

• State: (board id, node index, visited)
• Frontier: The collection of states that can be "stepped" e.g. moved to the next position in the trie

We start out with only 16 states (in the case of 4x4, one for each possible word starting point) and apply the "step" algorithm to each once. Because we can go many ways from each position we may end up with more than 16 next "states", e.g. we are at the second level in the trie and at different positions on the board.

This collection of "states" I call the frontier, it will in general grow as we go, then shrink as words end/hit dead ends. Our algorithm focuses on just moving all the points one "step" with minimal branching.

Core Arrays (cpp_ref)

// Direct child lookup (no bit twiddling)
int32_t childIndex[N*26];   // childIndex[u*26 + c] = child node or -1
uint8_t isTerminal[N];      // 1 if this node represents a complete word
int32_t termScore[N];       // Precomputed score for the terminal word at this node

Each node stores whether it is terminal and, if so, the score of the word that ends there in termScore[u]. Navigation is done via childIndex so there is no per-step bit manipulation.

How to navigate the trie (cpp_ref)

Use a direct 2D mapping indexed by (node, letter):

int child = childIndex[u * 26 + c];  // -1 if no such child

The childIndex array provides O(1) navigation per (node, letter) without per-step arithmetic.

Terminal scoring and de-duplication (cpp_ref)

When a traversal reaches a terminal node u, we add termScore[u] to the current board's total. To avoid counting the same terminal node multiple times on the same board (via different paths), we track the last board number seen per node and only add once per board.

Visited Bitmask

Each path through the board maintains a 32-bit visited mask where bit i is set if board position i has been visited

How the Frontier Works

1. Start from one of 16 positions, follow the first letter into the trie
2. At each depth, try all 8 possible neighbors
3. Skip neighbors that are:
   • Out of bounds (encoded as -1)
   • Already visited (check bitmask)
   • Not valid in the trie (child lookup returns -1)
4. When we reach a terminal trie node, record it