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$ 
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!
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.$$