# 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$.)

• It seems that a "benchmark" construction is to take strings of length $n_1+n_2-2$ and have, for $1\leq i <n_1$, a bit indicating whether the fist coordinate is strictly larger than $i$, and similarly for $1\leq j < n_2$ a bit indicating whether the second coordinate is larger than $j$. In other words for each horizontal and vertical line separating rows and columns of squares, there is a bit that flips exactly when you cross it. Mar 31 '14 at 5:14
• If $C$ is infinite, this seems to be essentially the only possibility. So the question is whether we can decrease $L$ if $C$ is finite. For $C=1$ we could have taken $L=1$ and the black/white chessboard pattern, but for some reason you don't like to have the same bit-string on different squares, is that right? Mar 31 '14 at 5:28
• @JohanWästlund Regarding not having the same bit pattern on different squares, right, I'd like all squares to have a unique bit string. It's what makes this question interesting to me actually. Mar 31 '14 at 6:06
• You want to assign the same binary string to each square??? Or was "unique" a typo for "different"????
– bof
Apr 4 '14 at 8:14
• @bof Is my english here incorrect? I thought "different unique binary string" would be implied? Apr 6 '14 at 7:26

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.

• In the proof of Lemma 5, you seem to apply the condition to the points $S_{0,C}$ and $S_{C,0}$, whose Manhattan distance is $2C$. So it seems that this idea allows to provo only that $L\geq [3C/2]$... Sep 17 '16 at 18:47