# Number of words which can be read at a grid

The task is to print all the words formed from the grid of characters, considering all the possible 8 directions (Right Horizontal, Left Horizontal, Top Vertical, Bottom Vertical, TopLeft Diagonal, TopRight Diagonal, Bottom Left Diagonal, Bottom Right Diagonal) from each character in the grid.

The grid can be rectangular and can be of any size like follows

a b c d
e f g h
i j k l
m n o p
q r s t


for example: Consider the letter 'j' from the array. Now for 'j', the possible combinations are as

Character itself    : j
Top Vertical        : jf, jfb
Bottom Vertical     : jn, jnr
Left Horizontal     : ji
Right Horizontal    : jk, jkl
Top Left Diagonal   : je
Top Right Diagonal  : jg, jgd
Bottom Left Diagonal: jm
Bottom Right Diagonal: jo, jot


Therefore for j, there are 14 possible words.

I want to know the total number of words that can be formed in a similar manner for all the characters given in the grid.

Is there any formula by which I can find out the total number of words that can be formed with the above scenario?

PS: I have already listed out the possible words using a JAVA program. Now I want to check whether my program has listed out all the possible words correctly.

• It is not clear what the task is. Do you need to use all the letters? If you printed some letter, say "j", does the next letter must be a neighbor letter like "e","f",g", "i", "k", "m", "n", or "o"? Please edit your question to clarify what you are asking. Commented Oct 30, 2016 at 0:42
• Do you mean all possible 4 letter unique words that can be formed considering all the mentioned directions ? Commented Oct 30, 2016 at 4:14
• I have edited the question by giving an example which I believe will make it quite clear. @SergioParreiras Commented Oct 30, 2016 at 6:41
• You want to know the total number of possible words for a given character (like for “j” in your example) or the total number of words which can be extracted from the grid in such the manner (for instance, for $2\times 2$ grid you have $4$ one-letter words and $12$ two-letter words, right?) Commented Oct 30, 2016 at 15:52
• Yes. I want to know the total number of words that can be extracted from the grid. Commented Oct 30, 2016 at 19:20

Let the grid be $m$ letters wide and $n$ letters high. We will assume $m \le n$, so interchange them if required.There are $mn$ one letter words. For horizontal words there are $m(m-1)$ ways to choose the starting and ending columns and $n$ ways to choose the row for $nm(m-1)$. Similarly for vertical words there are $mn(n-1)$. For diagonal words going down and to the right and length $k$ there are $(m-k)(n-k)$ possible starting letters. Summing over the lengths we get a total of $\sum_{k=2}^m (mn-(m+n)k+k^2)=(m-1)mn-(m+n)(\frac 12m(m+1)-1)+(\frac 16m(m+1)(2m+1)-1)$. There are four diagonal directions, so we multiply this by $4$. The grand total is $$mn+mn(m-1)+n(n-1)+4((m-1)mn-(m+n)(\frac 12m(m+1)-1)+(\frac 16m(m+1)(2m+1)-1))=\\-2 m^3/3 + 3 m^2 n + m n^2 - 7 m n + 14 m/3 + 4 n - 4$$
We have $mn$ words of length $1$. The remaining words belong to one of the straight lines: horizontal, vertical, and two diagonal. If a straight line consists of $l$ characters, then each of more than one letter word contained in it is uniquely determined by its the first and the last letter. Since there are $l(l-1)$ choices of pairs of such letters, we have exactly $l(l-1)$ contained in the straight lines. Now count how many straight lines of length $l$ we have. We have $n_1$ horizontal lines of length $n_2$ each and $n_2$ vertical lines of length $n_1$ each. To count the diagonal lines let $n=\min\{n_1,n_2\}$ and $N=\max\{n_1,n_2\}$. It is easy to check that for each of two diagonal directions for each $l<n$ we have $2l$ straight lines of length $l$, and have $N-n+1$ straight lines of lenght $n$. Thus the total number of words is
$$n_1n_2+n_1n_2(n_2-1)+n_2n_1(n_1-1)+4\sum_{l=1}^{n-1} l(l-1)+2(N-n+1)n(n-1)=$$
$$Nn+Nn(n+N-2)+4n(n-1)(n-2)/3+2(N-n+1)n(n-1)=$$
$$\frac n3\left(3N^2+9Nn-2n^2-9N+2\right).$$