Assigning unique binary strings to the squares of a chessboard s.t. inter-string Hamming distances are the same as inter-square Manhattan distances Consider a chessboard with $(n_1 \times n_2)$ squares, where we would like to assign a unique binary string, of some length $L$, to each square s.t. the Hamming distance between the strings corresponding to two squares on the board, $(s_a,s_b$), exactly corresponds to the Manhattan distance $H$ between $s_a$ and $s_b$ CONDITIONAL upon having $H \leq C$, where $C \in \mathbb{Z}$ is some integer constant.  
Knowing that $L \geq \frac{ln(n_1 \times n_2)}{ln(2)}$, what value for the minimum binary string length $L$ allows for this?  And is there a clever way to perform the string assignment for each square?  The problem becomes uninteresting for $C \approx max(n_1,n_2)$, but for small values of $C$, it seems like there could be a neat strategy to achieve small values for $L$ relative to what one might expect.
(I apologize.  When I previously asked this question, I specified that we should consider Chebyshev instead of Manhattan distances, and this is of course impossible for $(n_1,n_2) >1$.)
 A: Ignoring uniqueness, short answer is that for $\min(n_1, n_2) > C$ we need exactly $L = 2C$ bits.
When you want global uniquness, you can solve this with $L = \log_2 \left(\frac{n_1 n_2}{C^2}\right) + 2C$ bits. I can't claim it is optimal though.
But first, the non-unique case:
As a starting point, I thought of a $1$-dimensional problem, where instead of a $n_1 \times n_2$ board you have a $n_1 \times 1$ board, i.e., a row.
$1$-D case:
The problem will be to find a set of strings $\{S_0, S_1, S_2, ..., S_{n_1 - 1}\}$ such that for a given $C$ and any $i, j \ge 0$, $d_{H}(S_i, S_j) = |i - j|$ if $|i - j| \le C$ and an arbitrary value if $|i - j| > C$.
Let's start with $n_1 = C + 1$, and let $S_0, S_1, ..., S_C$ be such a sequence. Then, The sequence $S_0 \oplus S_0, S_0 \oplus S_1, ..., S_0 \oplus S_C$ is also such a sequence. As a result, we could look for the sequence with $S_0 = \mathbf{0}$, i.e., all zeros.
 Lemma $1$:  For $n_1 = C + 1$, $L^* = C$ and one optimal sequence is:
$$
 S_i = 0^{C-i}1^i
$$
where $x^i = \underbrace{xx...x}_{i \text{ times}}$.
 Proof: To get $d(S_{C}, S_0) = C$ we need at least $C$ bits. The sequence above has exactly $C$ bits.
Now lets consider the case $n_1 > C + 1$. 
 Lemma $2$:  For $n_1 = 2C$, $L^* = C$ and the sequence below is one solution:
$$
 S'_i = \left\{ \begin{array}{cc}
 S_i & i\le C \\
 \overline{S_{i - C}} & C < i < 2C
\end{array} \right.
$$
where $S_i$ is the same as the sequence in Lemma $1$ and $\overline{S_i}$ is the inverted string for $S_i$.
 Proof: From Lemma $1$, $L^* \ge C$. The given construction achieves $L = C$. Therefore, $L^* = C$.
 Lemma $3$ : For any $n_1 \ge C + 1$, $L^* = C$.
Proof: By Lemma $1$, $L^* \ge C$. Consider the sequence $S''_i$ as follows:
$$
S''_i = S'_{i \mod 2C}.
$$
Then $S''_i$ is a solution and with $L = C$. Therefore, $L^* = C$.
Now we can construct a suboptimal strategy for the $2$-Dimensional case:
 Lemma $4$ : For a $n \times n$ chessboard we have $L^* \le 2C$.
 Proof : Let $S(i, j)$ as the string in grid cell $(i, j)$. For two strings $X$ and $Y$, let $XY$ denote the concatenation of $X$ and $Y$. Now let $S_{i,j} = S''_iS''_j$. For any $(i, j)$ and $(k, l)$ we have
$$
 d\left( S_{i, j}, S_{k, l}\right) =  d\left( S''_i S''_j, S''_k S''_l \right)
 = d\left( S''_i, S''_k \right) + d\left(S''_j, S''_l\right) = |i - k| + |j - l|.
$$
On the other hand for $S_{i,j}$ given above we have $L = 2C$. Therefore, $L^* \le L \le 2C$. The inequality $L^* \ge C$ comes from Lemma $1$.
 Lemma  $5$: For the chessboard with $n_1 = n_2 = C + 1$ we have $L^* = 2C$.
 Proof : Let the length of a string be $L$ and $S_{0,0} = \mathbf{0}$. We must have:
$$
d(S_0, S_{i,C-i}) = C, \; i \in {0, 1, 2, ..., C}.
$$
Then each of the strings $S_{i, C-i}$ must have exactly $C$ ones and $L - C$ zeros. On the other hand, we must have
$$
d(S_{i, C - i}, S_{0, C}) = 2i
$$
Since the total number ones in both strings are the same, then we can only achieve this by flipping a one and a zero. For $C$ flips we need at least $C$ zeros in $S_{0, C}$ which suggests that $L^* \ge 2C$. This with Lemma $4$ proves that $L^* = 2C$.
As a corollary, for a general chessboard with $n_1 > C$ and $n_2 > C$ we find that $L^* = 2C$. 
The Unique Strings Case
Let's move back to Lemma $2$ and reconsider the sequence $S'_i$. Take prefix $X_k$ and consider the sequence below:
$$X_kS'_0, X_kS'_1,...X_kS'_{2C - 1}, X_{k + 1}S'_{2C - 1}, X_{k + 1}S'_0, ...$$
Let's assume that for all $k$, $d(X_{k}, X_{k + 1}) = 1$. Then the sequence above satisfies the Manhattan distance constraint. See that:
$$ 
\begin{array}{c}
   d(X_k S'_{2C - 1}, X_{k + 1} S'_{2C - 1}) = 1 \\
   d(X_{k + 1}S'_{2C - 1}, X_{k + 1}S'_i) = i \\
   d(X_{k}S'_{2c - i}, X_{k+1}S'_{j}) = 1 + d(S'_{2C - i}, S'_{j}) = 1 + |i - j|
\end{array}
$$
which are all valid in terms of their Manhattan distance.
$X_k$ could be any grey-coded sequence of length $n$ and hence, with length $n + 2C$, we can make $2^{n} \times (2C)$ strings. As a result, the length required for building $N$ strings  is $\log_2\left( \frac{N}{C} \right) + C + 1$. 
Note that for small $C$, this is asymptotically optimal. For $2D$ we can follow the same pattern as that of Lemma $4$ and $5$ and come up with $\log_2 \left( \frac{n_1n_2}{C^2} \right) + 2C$. Again for small $C$, I guess, the method gives a tight bound.
