Suppose we have an $n \times n$ square, and an alphabet $\Gamma$. We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location. The constraint is that a pair $a,b$ of neighbors (either east-west of each other, or north-south of each other) can only appear in that configuration once.
Example of a prohibited square:
a b c
d e f
g d e
Since "de" appears on both the second and the third row, the entries of the square are not acceptable. The same problem would arise if, say, a appeared above d anywhere except the top left corner.
Given $n$, the width of the square as a parameter, what is a lower bound on the size of the alphabet $\Gamma$?
I would love (suggestions toward) a direct proof, but also, has this type of square-filling problem been studied? I can't connect it to either a Latin square, or a block design. Does this map onto any already-named combinatorial object?
(Note: this is related to a previous question of mine about avoiding partial words, but that question only required avoidance east-west, so to speak, whereas here I need to avoid north-south repetitions also.)