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: