# Finding a string with some specified hamming distances from other strings

I'm searching the space of length $n$ strings (a-z lowercase), which I suppose we could represent as a large graph of strings and hamming distances between the strings.

I'm given some pairs of strings and distances $v_i, d_i$ . I need to find a string which has distance $d_i$ from each each string $v_i$ .

Does there exist an efficient algorithm for finding this? Perhaps it's possible to triangulate to the right string?

• How many pairs do you have? The problem might become simpler if you have only a few pairs. Nov 20, 2017 at 19:34
• I'm dealing with a variant of mastermind where you can make a guess against the true string and find out the distance of that guess. Goal is to minimize number of guesses. In my experience trying a greedy guess approach, it takes a few dozen guesses for a string of length 10-15. Nov 20, 2017 at 19:39
• You should include all information relevant to your question in your post. Otherwise we will provide an answer which won't satisfy you, you will modify your question, we will have to provide another answer which won't satisfy you, and so on. Nov 20, 2017 at 19:40
• I was specifically interested in my original question rather than a discussion of strategies for this game. If you feel I should reformulate the question completely, should I make a new one? Nov 20, 2017 at 19:43

The decision version of your problem that I will analyze asks whether there is an answer. The problem is clearly in NP, and we prove that it is NP-hard by reduction from X3SAT, a variant of 3SAT in which a formula is satisfiable if every clause contains exactly one satisfied literal. Given a 3CNF on $n$ variables $x_1,\ldots,x_n$, we will consider strings of length $2n$ which encode a truth assignment: a 1 in position $2(i-1)+1$ encodes that $x_i$ is true, and a 1 in position $2(i-1)+2$ encodes that $x_i$ is false.
In order to force that any solution must have exactly one 1 in each of the positions $2(i-1)+1,2(i-1)+2$, we ask that it have distance $n$ from the strings $(00)^n$ and $(00)^{i-1}(11)(00)^{n-i}$ for $1 \leq i \leq n$. In order to force any solution to satisfy all clauses, for every clause we take the string which has 1s in the positions corresponding to the literals in the clause, and we ask that the solution be at distance $(n-3)+2$ from this string. A string satisfies these $n+m+1$ constraints (where $m$ is the number of clauses) if and only if it is a satisfying assignment to the given 3CNF.