Minimum Size of Word Search Containing All Strings of Length $l$

Question

The following is a problem I came up with and have been thinking through for the last several days, making little progress. The problem statement is deceptively simple, and (unless I'm missing something), the problem itself proves to be fairly difficult.

Consider a $m * n$ grid, with $m$ rows and $n$ columns. Each element in this grid can contain one of $k$ letters. We will denote such a construction a word search. What is the minimum size of a word search that contains all strings of length $l$? Size here is defined as area, or $m*n$. Furthermore, you can find a string looking left, right, up, down, or diagonally, and strings can overlap.

My progress: We first note that there are $k^l$ possible strings of length $l$. Therefore, we could take the trivial construction of a $k^l * l$ grid, each row containing one unique string of length $l$. However, this is inefficient in several ways. First, noting that we can read strings backwards as well as forwards, we can immediately cut the number of rows by almost a half (strings which are palindromes can't be cut). Also, this doesn't even begin to account for the number of ways we can look at strings vertically (both upwards and downwards), and diagonally.

I also noted that the optimal construction will probably be a square, or close to it. My reasoning for this is because if we have a $m * n$ grid, assuming WLOG that $m < n$, note that adding one row will increase the net number of strings present by more than adding another column.

One possible idea is to use a greedy algorithm that operates as follows: 1) Construct a set of all $k^l$ strings. We will use this to track progress - every time we add a new string to our search, we will remove it from the set, and our goal is to empty the set. 2) Create an empty $l * l$ grid. 3) Consider all possible ways to populate that grid with each of the $k$ letters in each element, and choose the population that minimizes the size of the set (ie removes the most number of strings from the set). 4) Recursive step: let the size of the grid be $n * n$ currently. Consider all possible additions of $2n+1$ letters, adding $n$ letters below the last row, $n$ the the right of the last column, and the remaining $1$ to fill in the square. Whichever one decreases the set size the most is chosen. Repeat this until we're done. This algorithm is clearly not perfect, as it requires the right choice of a kernel, and also could be very inefficient towards the end.

We can also use this same algorithm, but instead of adding the L shape at the bottom right, we can surround the entire thing with a square. This may yield more accurate results.

I'd appreciate any ideas, from establishing an upper/lower bound on the size combinatorically, to finding an algorithm, or any sort of geometric/algebraic approach. I'm not sure if probabilistic method would be helpful here, but after reading into it I think it may be. All progress will be really helpful!

The following are a few similar, slightly easier, problems to get some ideas from:

What is the shortest string that contains all permutations of an alphabet?

Expected length of a sequence that contains all words of a given length.

Answer 1

For notational ease, let $W(k,l)$ be defined to be the size of the smallest grid that holds all $k^l$ strings as specified.

A clear solution for $(k,l) = (2,2)$ is \begin{pmatrix} AB \\ BA \end{pmatrix} though this is by no means difficult to find. This structure can be used to find more upper bounds for $W(k,2)$. An example for $k = 4$ is given below.

\begin{pmatrix} DCAB \\ CDBA \end{pmatrix}

It is clear that $W(k,l) \geq l^2$, and for odd $l$, $W(k,l) > l^2$. The proof of the second of these follows form the observation that placing the string of all A's in any orientation in an $l \times l$ grid forces an A into every other possible string of length $l$ if $l$ is odd and allows only for the other diagonal to be the string of all Bs if $l$ is even. In the case $k = l = 2$, the construction succeeds, and it obviously fails if $k > 2$. If $l > 2$, then the attempted construction would look like

\begin{pmatrix} A X X & \dots & X X B \\ \vdots & AB & \vdots \\ \vdots & BA & \vdots \\ B X X & \dots & X X A \\ \end{pmatrix}

Now, every column and row contains an A and a B. Consider inserting the string with 2 central Bs and all other characters A. There is no place this can be inserted, as stated. Therefore, $W(k,l) > l^2$ for all $k,l > 2$.

This proof lead me to attempt non-square solutions, and I have found the following solution for $(k,l) = (2,3)$;

\begin{pmatrix} ABBB \\ AABX \\ ABAX \end{pmatrix}

where X is an arbitrary character. This suggests that $W(2,3) = 12$, and certainly that $W(2,3) \leq 12$. The shape of this construction would lead to a conjecture that for $l > 2, W(2,l) \leq l(l+1)$. An inductive proof would be natural to continue the problem. Now, we argue for this statement by demonstrating an algorithm to lift a construction for $l$ to $l+1$ (note: this construction is slightly flawed, see comments at end)

Consider the solution given above for the case $l = 3$. Now, lift the first column and row of the $3 \times 4$ region to create a $4 \times 5$ region (we place O where new space appears)

\begin{pmatrix} ABBBO \\ AOOOO \\ AOABX \\ OOBAX \\ \end{pmatrix}

Now, clearly the bottom left O must be an A and the top right O must be a B. We also suppose that the O furthest right is arbitrary, and denote this with X. Now, we have

\begin{pmatrix} ABBBB \\ AOOOX \\ AOABX \\ AOBAX \\ \end{pmatrix}

Observe that this process has recreated each all-A and all-B strings and has effectively split every string 123 from the previous construction into the string 1023 (or alternatively 3201). Let the corner O be an A (chosen to maintain symmetry) and, starting from the bottom of L shape of Os, chose the Os to be B or A, starting with B and alternating. We then obtain

\begin{pmatrix} ABBBB \\ AABAX \\ AAABX \\ ABBAX \end{pmatrix}

which contains every string of length 4 in two letters. This strategy works because the columns and rows of this grid share a symmetry - before the insertion, row 4 and column 3 were opposite strings, so inserting B in each guarantees a different string for each, and similarly with row 3 and column 4. I believe that this sort of algorithm (creating an L and filling it in) will generate all solutions, but I cannot pin down what the algorithm is precisely for higher $l$.

Now, for $k = 3$, I have found that $W(3,2) = 6$ (not hard to find). I the problem continues to have the same kind of structure as it did for $k=2$, I would conjecture that $W(3,3) = (3+1)(3+2) = 20$.

A similar pattern seems to hold for $k = 4$, simply because constructions for $k=2,3,4$ and $l = 2$ are very similar. However, for $k > 4$, it becomes less obvious what $W(k,2)$ might be. From messing around, I am inclined to believe that $W(5,2) = 12$, given the construction

\begin{pmatrix} ABBD \\ AEED \\ DCCA \end{pmatrix}

and the difficulties in trying to establish any other grid that works.

NOTE: I realize now that my "proof" that $W(2,l) \leq l(l+1)$ is flawed. However, I have decided to leave the faulty proof up as a reference, because I believe that, algorithmically, the method of creating L shapes is a good greedy algorithm for this problem. This is similar in many ways to the algorithm offered by the author, except that the L created is internal and that we start work with a near-square instead of a square.

The best genuine upper bound I can think of as of yet would be the following;

Given a copy of a grid solving $W(k,l-1)$, we can create a copy of this grid, rotate it 90 degrees, and place it to the right of the initial copy with one column of empty space. Fill that empty column with Bs and cap the right and left ends of the shape with columns of As. This process is a geometric means of achieving the property that all length $l$ words consist of a starting A or B with any $l-1$ word following. If we let $W(k,l-1) = rc$ with $r$ representing rows of the grid and $c$ representing columns, we can write the inequality

$$W(2,l) \leq (2r+3)c = 2W(2,l) + 3c$$

Clearly, this is a very inefficient method, and it is recursive, which is doubly annoying and not useful. But it is the strongest upper bound I could rigorously construct. This inequality could easily be extended to $k$ other than 2, but it wouldn't really be that helpful.

Given my greedy algorithm, I would make the following conjecture about the true value of $W(k,l)$;

There exists some function $a : (k,l) \to \mathbb{N}$ such that when one of $k,l$ is bigger than 2; $$W(k,l) = (l + k - 2 + a)(l + k - 1 + a)$$

which is to say that the best scenario is always a square with a single column added.