[Math] Counting Valid Strings in Will Shortz 3D-Word Hunt

combinatoricsrecreational-mathematics

So I was reading the NY Times Magazine (only the puzzle section of course) and I came across a puzzle I had never seen before. Titled the "3D-Word Hunt", the goal is to find as many five letter words as possible in a $2 \times 3 \times 3$ array of letters. You are allowed to repeat letters, but you cannot stall and repeat.

Below is an example puzzle.

$\hskip2in$ enter image description here

To clarify the rules, an acceptable word would be "DETER" and an $un$acceptable word would be "ADDER".

In the aforementioned puzzle in the NY Times I found 32 English words. But then I thought of another (arguably harder) question:

How many acceptable five letter strings are there?

(So, disregard the requirement that the string be an actual English word)

I have always struggled with tricky counting problems, so I come to you looking for an elegant solution. I feel like there should be some dynamic program to solve this question (first find all five letter words that do not travel more than $n$-steps from the first letter with $n \in \{1, 2, 3, 4, 5\}$), but my results have been inconclusive.

Happy holidays!

Best Answer

It is a graph theory problem. All necessary information of the array can be translated into a graph $G$ were letters are nodes and words are paths. We are interested in the number of 5-paths in $G$.

This number can be calculated by using the adjacency matrix $A$ of $G$: The number of paths of length $n$ starting with vertex $i$ and ending with $j$ is $(A^n)_{i,j}$. So the number $N_n(A)$ of $n$-paths in $G$ is given by the sum of all matrix elements of $A^n$, or in terms of linear algebra:

$$N_n(A)=e A^ne^t$$ where $e=(1,...,1)$. In your example, $$S_5(A) = 13970.$$

Related Question