# What sequence of letters am I thinking of? (Or: Introducing "Bulls")

## 1. Warmup

"I'm thinking of three letters," I grinned, "in a particular order, and with no repeats."

"Are they DRL?"

"Well, you guessed one correctly."

"Are they QYL?"

"You guessed one correctly."

"QBN?"

"One."

"PFE?"

"One."

"QSH?"

"One. That's enough guessing; you can figure it out now."

This is of course a non-word, black-peg-only variation on Word Mastermind, or an alphabetical, bulls-only version of Bulls and Cows. I'll dub it simply "Bulls".

The three following puzzles are of increasing difficulty; I had to use a computer to help me solve the final, eight-letter one.

Obviously, if you were actually playing this as a guessing game, there'd be a lot more complete misses, and, unless you were very lucky, more guesses would be required. These were designed to be just-solvable with a minimum of clues.

Have fun!

## 2. A little more difficult

"I'm thinking of four letters in a particular order, with no repeats."

"FGTI?" --"One."

"EDOY?" --"One."

"JMEY?" --"One."

"QHYO?" --"One."

"NGRC?" --"One."

"XUVT?" --"One. That's enough!"

## 3. A little more difficult still

"I'm thinking of five letters ..."

"CHVIE?" --"One."

"UILJR?" --"One."

"RMNTZ?" --"One."

"EFWAR?" --"One."

"MTVOJ?" --"One."

"GZEDC?" --"One."

"KENDT?" --"One."

"PDKQG?" --"One."

## 4. Really rather difficult perhaps

"Eight letters ..."

"VKGYXWCT?" --"One."

"XBLARNFT?" --"One."

"XRYQDBIW?" --"One."

"UNCZBVPO?" --"One."

"DLCZEPTG?" --"One."

"MDPUEQCJ?" --"One."

"JPGAZTHQ?" --"One."

"ZKMWEPRG?" --"One."

"LXFYGTVH?" --"One."

"IABGDESW?" --"One."

"XCTFELAQ?" --"One."

"ZUCOQLRV?" --"One."

"YBXPSTHI?" --"One."

"MJEOKICY?" --"One."

"DVAFRYHE?" --"One."

"VTRUFEQN?" --"One."

The first three are very easy to solve without a computer:

Just pay attention to where two or more guesses have the same letter in the same spot.

1:

Q must be the first letter. There are three guesses that start with Q and only have one correct. If Q isn't the correct first letter, then either the second or third letter must have been correctly guessed by more than one of those three guesses. However none of them overlapped on the second or third letter, so that is not possible.

R must be the second letter. DRL has one letter correct, and because we know the Q of QYL is the correct letter, L is not the last letter.

E is the last letter. PFE has one letter correct, and it's not the first or second letter.

QRE

2:

With six guesses and four letters, two of the guesses must have each gotten the same letter correct as one of the other guesses. If you look at all the guesses, there are only two pairs that have an overlap - FGTI & NGRC, and EDOY & JMEY. So the overlaps must be correct - _G_Y

The two remaining guesses reveal the first and third letters. We already have a Y in the answer, so QHYO's third letter can't be correct.

QGVY

3:

We again have more guesses than letters, so we'll start by seeing where there are overlaps. UILJ(R) & EFWA(R) and CH(V)IE & MT(V)OJ pair up, and KE(ND)T pairs with each of GZE(D)C and RM(N)TZ. With five letters and eight guesses, there must be 3 pairings. If KENDT paired on the third letter, D would be incorrect and CHVIE & MTVOJ wouldn't be paired on a correct third letter, leaving only two pairings. So we have __VDR, and RMNTZ doesn't get a pairing.

With only two guesses left, we're in the same situation as in #2. RMNTZ and PDKQG can only fit in in one way.

PMVDR

1. I wasn't able to solve this one very cleanly, but following the same strategy as before allowed me to solve it eventually:

It's quite a bit messier this time - from the 16 guesses we need 8 pairings, but there are 29 letters that can be paired on. Some of those letters have 3 or 4 guesses that use them.

There's only one case where four guesses share a letter (E as the fifth letter), so that seems like a good place to start. Then we can use those four guesses to narrow things down a bit - any other guess that shares a letter with one of those guesses can't be correct on that letter, and E can't be anywhere else.

At this point my information looked like this:

What you see here is all the E clues together, and all the other clues with known-incorrect letters replaced with a dash. The other clues are also arranged in a crude graph of possible pairings.

????E???

MDPUEQCJ
XCTFELAQ
DLCZEPTG
ZKMWEPRG

VTR---QN
V-GY-W-T
JPGA-TH-   LXFY-TVH
-BLA-NFT   YBXP-THI
-VA--YH-

UN---VPO

-RYQ-BIW
IABG--SW

-J-O-I-Y
-U-O---V

At the bottom there is one guess with no remaining pairings, and two isolated pairs. Taking those two pairings as correct maximizes the number of choices for the messy bit, giving us ???OE??W so far.

From here I just took a couple guesses that worked out. I chose V as the first letter and T as the sixth for V??OET?W. This constrained the rest of guesses enough for me to get the last three letters.

VNAOETFW

We can use integer programming to solve this quite nicely.

Call the set of clues $$C$$, and call the $$i$$-th letter of a clue $$c\in C$$ be $$c_i$$. If the number of letters is $$n$$ then $$1\le i\le n$$. Now, for a given position $$i$$ and a letter $$\ell$$, let $$x_{i,\ell}$$ be $$1$$ if the $$i$$-th letter of the solution is $$\ell$$, and $$0$$ otherwise. Now our constraints are:

• Exactly one letter much be picked for each position: $$\sum_{\ell\in\{A\ldots Z\}} x_{i,\ell}=1\qquad(1\le i\le n)$$
• Each letter can be picked at most once (this is only stated as a requirement for 2. but is needed for all of the given problems to have a unique solution): $$\sum_{i=1}^n x_{i,\ell}\le 1\qquad(\ell\in\{A\ldots Z\})$$
• Each clue must have exactly one correct letter: $$\sum_{i=1}^n x_{i,c_i}= 1\qquad(c\in C)$$

These are all linear constraints so any ILP solver will be able to find a solution. Here is some python code to solve problem 4 with SCIP:

import pyscipopt as scip
from string import ascii_uppercase as alphabet

clues = ["VKGYXWCT", "XBLARNFT", "XRYQDBIW", "UNCZBVPO", "DLCZEPTG", "MDPUEQCJ", "JPGAZTHQ", "ZKMWEPRG", "LXFYGTVH", "IABGDESW", "XCTFELAQ", "ZUCOQLRV", "YBXPSTHI", "MJEOKICY", "DVAFRYHE", "VTRUFEQN"]

n = len(clues[0])

model = scip.Model()
x = [{l: model.addVar(f'x#{i}#{l}', vtype='BINARY') for l in alphabet} for i in range(1, n+1)]
for letter_vars in x:
for l in alphabet:
model.addCons(scip.quicksum(letter_vars[l] for letter_vars in x) <= 1)
for clue in clues:
model.addCons(scip.quicksum(x[i][l] for i, l in enumerate(clue)) == 1)

model.optimize()
solution = ''.join(l for vars in x for l, var in vars.items() if model.getVal(var) > 0.5)


Even 4. is solved instantaneously by this method. Here are the solutions:

1:

QRE

2:

QGVY

3:

PMVDR

4:

VNAOETFW

• "Each letter can be picked at most once (this is only stated as a requirement for 2. but is needed for all of the given problems to have a unique solution)". In fact, stated for 1 and 2, but hopefully adequately implied (by ... elipses) for 3 and 4. Thanks for the great answer! Oct 30, 2021 at 21:55

I also wrote a program. The answers are

1. QRE 2. QGVY 3. PMVDR 4. VNAOETFW

Here is the source code for anyone curious:

class BullSolver
{
public:
void addString(std::string const &s, int correctCount)
{
strings_.push_back(s);
counts_.push_back(correctCount);
charBank_.resize(max(charBank_.size(), s.size()));

for (int charIndex = 0; charIndex < s.size(); charIndex++)
{
charBank_[charIndex].insert(s[charIndex]);
}
}

void solve()
{
int len = charBank_.size();

std::vector<std::set<char>::iterator > charIters(len);
std::vector<char> charValues(len);

for (int charIndex = 0; charIndex < len; charIndex++)
{
charIters[charIndex] = charBank_[charIndex].begin();
charValues[charIndex] = *charIters[charIndex];
}

while (true)
{

bool duplicate = false;

for (int charIndex = 0; charIndex < len; charIndex++)
{
for (int other = charIndex + 1; other < len; other++)
{
if (charValues[charIndex] == charValues[other])
{
duplicate = true;
}
}
}

if (!duplicate)
{

bool matching = true;

for (int strIndex = 0; strIndex < strings_.size(); strIndex++)
{
int corrects = 0;

for (charIndex = 0; charIndex < len; charIndex++)
{
if (charValues[charIndex] == strings_[strIndex][charIndex])
{
corrects++;
}
}

if (corrects != counts_[strIndex])
{
matching = false;
break;
}
}

if (matching)
{
for (charIndex = 0; charIndex < len; charIndex++)
printf("%c", charValues[charIndex]);
printf("\n");
}

}

bool increment = true;

for (charIndex = 0; charIndex < len; charIndex++)
{
if (increment)
charIters[charIndex]++;

if (charIters[charIndex] == charBank_[charIndex].end())
{
charIters[charIndex] = charBank_[charIndex].begin();
increment = true;
}
else
{
increment = false;
}

charValues[charIndex] = *charIters[charIndex];
}

if (increment)
break;

}

}

private:
std::vector<std::string>    strings_;
std::vector<int>            counts_;
std::vector<std::set<char> > charBank_;

};

int main(void)
{
{
BullSolver bs;

bs.solve();
}

{
BullSolver bs;

bs.solve();
}

{
BullSolver bs;

bs.solve();
}

{
BullSolver bs;

bs.solve();
}

return EXIT_SUCCESS;
}


It's a quick and dirty brute force that makes some assumptions but it worked for the job.

• Unless I'm missing something this answer concisely answers OP's only question: "What sequence of letters am I thinking of?" While the other answer here is clearly a better answer, you can know that I didn't copy from it by rot13(ybbxvat ng gur gvzrfgnzcf). When I said 'also', I meant rot13(whfg yvxr BC, nf gurer jrer ab nafjref ng gung gvzr). I will add my code to the answer. Oct 27, 2021 at 18:06
• My apologies; I failed to inspect the timestamps during my review. I will remove my comments, though it's too late for my flag. Upvoted. Oct 27, 2021 at 19:01
• This solution does not deserve negation. Please, fellow puzzlers, do not snub programmable responses as such. Providing verity as well as being well puzzled out these also teach us how to code a puzzle.
– humn
Oct 27, 2021 at 19:41