Playing Mastermind with Wordle-like Feedback

Abstract

We introduce an extension of Mastermind called Clear Mastermind with enhanced feedback inspired by that from Wordle. The only difference between Clear Mastermind and Mastermind is a rule that provides more precise feedback, as found in Wordle. In Clear Mastermind, the feedback contains the positions of the colors the codebreaker guessed correctly and the positions of colors that appear in the answer but in different positions. We explore the fewest number of guesses that a codebreaker requires to find the answer in Clear Mastermind according to its two parameters: the number of colors and the length of the answer.

MSC:

• 05-08
• 05A05

Introduction

Background

Mastermind is a popular code-breaking game for two players. One player, the codemaker, selects a secret color sequence of four pegs from six possible colors. The other player, known as the codebreaker, attempts to deduce the codemaker’s sequence with minimal guesses by utilizing corresponding feedback. Each guess is a sequence of four colored pegs picked from the six color alternatives. The feedback includes the number of pegs the codebreaker guessed correctly and the number of pegs that are of the right color yet not in the right position. The game has been studied from a computational perspective [1–4].

Wordle is a single-player code-breaking game where the player tries to guess a five-letter English word chosen by the computer. It is similar to Mastermind where the player tries to guess a color combination. In Wordle, however, the player must guess a valid five-letter word in English for each guess. The feedback in Wordle is more specific than in Mastermind, as it provides the exact positions of correctly guessed letters and the letters that appear in the answer but in different positions. The online game has gained immense popularity and many studies have explored different ways to interpret the game [5, 6]. It is worth noting that the game has been proven to be NP-complete [7, 8]. Specifically, the possible target words and allowable guesses in Wordle are restricted sets. The game we define in this article is a special case of Wordle in which target words and allowable guesses contain all possible sequences of k characters.

Additionally, Hamkins [9] has studied the infinite number of variations of both Wordle and Mastermind, with some of his ideas overlapping with the approaches used in this article. While Hamkins’ work is more related to axiomatic set theory, this article focuses on combinatorial problems.

In this paper, we introduce Clear Mastermind, which combines aspects of both Mastermind and Wordle. Conceptually, Clear Mastermind is Mastermind with Wordle’s feedback.

We define Clear Mastermind with $n\ge 1$ positions and $k\ge 1$ letters representing the colors as a two-player game as follows. Let us denote by $[k]$ the set $\{1,2,\dots ,k\}$ of positive integers. One player, the codemaker, initially selects a secret answer $y=(y_1,y_2,\dots ,y_n)\in {[k]}^n$ in letters from an alphabet $[k]$ to be the answer in the game, with y_i being the letter on the ith position of the answer (ith letter of the answer for short). The other player, the codebreaker, attempts to find the answer by guessing a series of words. In each round, the codebreaker guesses a word $x=(x_1,x_2,\dots ,x_n)\in {[k]}^n$. The codemaker then provides feedback by coloring each letter of the word either Green, Yellow, or Black based on how each letter matches the secret answer. The feedback provides the codebreaker with the commonalities between the secret answer y and the guessed word x in each round, allowing them to narrow down the list of words possible to be the answers and make better guesses in the following rounds. The feedback rules will be further explained in the following section. If the codebreaker’s guess matches the answer in the ith round, we say that the codebreaker finds the answer in i rounds or that the codebreaker solves the puzzle in i rounds.

Feedback Rules

First, any letter of x that matches with a letter of y such that x_i = y_i is colored Green. Next, consider the unmatched letters in x and y. For each $j\in [k]$, if j has n_j unmatched occurrences in y and m_j in x, then the first $\mathrm{\text{min}}(n_j,m_j)$ unmatched occurrences of j in x are colored Yellow. All remaining entries of x are colored Black. Two examples of Clear Mastermind are illustrated below.

For convenience, we denote the feedback by a sequence made up of Green(G), Yellow(Y), and Black(B). Let $\pi (x|y)\in {\left\{\text{G,Y,B}\right\}}^n$ denote the feedback for the guess x given the answer y. Define the answer set P_i $$\begin{array}{c}{P}_0={\left[k\right]}^n,\\ P_i=\{w\in P_{i-1}:\pi (x^{(i)}|w)={\tilde{\pi }}^{(i)}\},i\in \mathbb{N},\end{array}$$where $x^{(i)}$ and ${\tilde{\pi }}^{(i)}$ is the guess and the feedback of the ith round respectively.

The answer set P_i is a function of the previous guesses and feedback. Intuitively, the answer set P_i is the set of words that are still possible to be the secret answers for the codebreaker after i rounds. By definition, we have $P_{i+1}\subset P_i,\text{ where }i\in \mathbb{N}$.

Here is an example to explain the answer set:

• For $k=3,n=3$, the codebreaker guesses (1,2,3) in the first round and receives the feedback $\pi =$ (G,G,B), then the answer set P₁ would be {(1,2,1),(1,2,2)}. In the second round, the codebreaker guesses (1,2,2) and receives the feedback $\pi =$ (G,G,B), then the answer set P₂ would be {(1,2,1)}, which means that the answer is (1,2,1). The codebreaker finds the answer in 3 rounds then.

Our Contribution

Define F(k, n) as the fewest number of guesses that the codebreaker requires to find the answer in Clear Mastermind with n positions and k letters.

In Clear Mastermind, the codebreaker can guess by using the following strategy. In the jth (j < k) round, the codebreaker guesses ($j,j,\dots ,j$) $\in {[k]}^n$. After the codebreaker receives the feedback in the $(k-1)$th round, the answer set $P_{k-1}$ contains only one word and the correct answer is deduced. So, the codebreaker can solve the puzzle in the kth round, which means $\text{ for all }k,n\in \mathbb{N},$ (1) $$F(k,n)\le k$$(1)

In this work, we prove the following results:

Theorem 1.

1. If $k\le n$,

   $F(k,n)=k.$

2. If k > n and n divides k,

   $F(k,n)=\frac{k}{n}+n-1.$

3. If k > n and n does not divide k,

   $\lfloor \frac{k}{n}\rfloor +n-1\le F(k,n)\le \lfloor \frac{k}{n}\rfloor +n.$

The main results show that finding an optimal strategy in Clear Mastermind is nearly trivial, while in Wordle where guesses and target words are restricted, finding an optimal strategy is computationally intractable [7, 8].

We prove the three cases in the following three sections.

1 The First Case

In the case $k\le n$, in order to prove Theorem 1, it is sufficient to prove $F(k,n)\ge k$ from the inequality (1).

It is challenging to deal with feedback that includes Yellow because it provides information that is hard to utilize. One intuitive idea is that if we know the frequency of each letter $j\in [k]$ in the secret answer y, then the feedback of Yellow is unnecessary. The formal expression is discussed later in Proposition 2. Define the feedback $$\tau (x|y):=({\tau }_1(x|y),{\tau }_2(x|y),\dots ,{\tau }_n(x|y))\in {\{✓,✗\}}^n$$with ${\tau }_i(x|y)=$ ✓ if x_i = y_i and ${\tau }_i(x|y)=$ ✗ if $x_i\ne y_i$. We show that the feedback $\pi (x|y)$ is equivalent to the feedback $\tau (x|y)$ if we know the frequency of the letters in y.

Given a word y, let $\omega (y)=({\omega }_1(y),{\omega }_2(y),\dots ,{\omega }_k(y))\in {\mathbb{N}}^k$ be the frequency vector of y, where ${\omega }_j(y)$ is the number of occurrences of letter j in y.

Proposition 2.

If the codebreaker guesses a word x, and knows the frequency vector of the secret answer y, then the codebreaker can deduce $\tau (x|y)$ based on the provided $\pi (x|y)$, and vice versa, the codebreaker can deduce $\pi (x|y)$ given $\tau (x|y)$.

Proof.

On the one hand, it is easy to obtain $\tau (x|y)$ when the codebreaker knows $\pi (x|y)$. Convert every Green in $\pi (x|y)$ to ✓in $\tau (x|y)$ and every Yellow and every Black to ✗, and the codebreaker obtains the feedback $\tau (x|y)$.

On the other hand, given $\tau (x|y)$, the codebreaker may obtain $\pi (x|y)$ as follows. Convert every ✓in $\tau (x|y)$ to Green in $\pi (x|y)$. Next, for each $j\in [k]$, let l_j count the number of Green occurrences of j in x. Color the leftmost $\mathrm{\text{min}}({\omega }_j(y),{\omega }_j(x)-l_j)$ occurrences of j in x Yellow. Color the remaining entries of x black. The codebreaker obtains the correct feedback $\pi (x|y)$. □

Thus, in the case that n = k and the answer is known as a permutation of $\{1,2,\dots ,k\}$, we consider the game that the codemaker alternatively provides the codebreaker with feedback $\tau (x|y)$, which has the same difficulty with the one that the codemaker provides the feedback $\pi (x|y)$. Define G(k) as the fewest number of guesses that a codebreaker requires to find the answer in the case that n = k and the answer is known to be a permutation of $\{1,2,\dots ,k\}$, while receiving the feedback $\tau (x|y)$ from the codemaker.

In the case n = k, we know that $$F(k,k)\ge G(k)$$because in the game with k positions, k letters, and the public information that the answer is a permutation of $\{1,2,\dots ,k\}$, the codebreaker can pretend not to know the public information and then solve it within F(k, k) rounds.

In the case k < n, let $y=(y_1,y_2,\dots ,y_n)$ be the answer for a game with k positions and n letters. We, as the codemaker, set $y_j=1$ if j > k and set $(y_1,y_2,\dots ,y_k)$ to be a permutation of $\{1,2,\dots ,k\}$. Make the information above public. Under such circumstances, the codebreaker still needs at least G(k) rounds to solve the game in the case k < n, which means $$F(k,n)\ge G(k),k<n.$$

Thus the first case of Theorem 1 can be deduced from the following proposition.

Proposition 3.

$G(k)\ge k,\text{ for all }k\in {\mathbb{N}}^{*}$.

In the remaining content of the section, we will always focus on the Clear Mastermind game with k positions, k letters, and the public information that the answer is a permutation of $\{1,2,\dots ,k\}$. The codemaker provides the codebreaker with feedback $\tau (x|y)$.

For any codebreaker, we, as the codemaker, aim to find a word to be the answer and prove that the codebreaker cannot solve the puzzle in k – 1 rounds. In fact, we do not have to commit to a definite answer of the game in advance. As the game proceeds, we can choose another word as the answer of the game, as long as it remains consistent with all the previous guesses and the feedback.

As a result, the codemaker only needs to provide feedback by using a specific strategy after each round and ensure that the answer set is not empty. The less information from the feedback that is given to the codebreaker, the better the strategy. Intuitively, the specific strategy is to provide ✗ by a greedy algorithm. It checks whether the next position of the feedback can be filled with ✗ without contradictions. If it can, fill with ✗ and go on to the next position; otherwise, fill with ✓and go on.

Before providing a more detailed explanation, we extend the definition of the answer set. Define the Q-answer set $Q_{i,j}$ $$\begin{array}{c}{Q}_{1,0}={\left[k\right]}^n,\\ Q_{i,0}=Q_{i-1,n},i\in \{2,\dots ,n\},\\ Q_{i,j}=\{w\in Q_{i,j-1}:{\tau }_j(x^{(i)}|w)={\widetilde{{\tau }_j}}^{(i)}\},i\in [n],j\in [n],\end{array}$$where $x^{(i)}$ and ${\tilde{\tau }}^{(i)}=({\widetilde{{\tau }_1}}^{(i)},{\widetilde{{\tau }_2}}^{(i)},\dots ,{\widetilde{{\tau }_n}}^{(i)})$ are the guess and the feedback of the ith round, respectively.

Intuitively, $Q_{i,j}$ is the set of words possible to be answers considering the guesses and the feedback in the initial i – 1 rounds, and the guesses and the feedback in the initial j positions of the ith round. Notice that $P_i=Q_{i,n}=Q_{i+1,0}$. An example is shown below:

• In a Mastermind game with $k=3,n=3$, the codebreaker guesses (1,1,1) in the first round, and the feedback is (✗,✓,✗). In the second round, the codebreaker guesses (2,1,2), and if the feedback is (✓,✓,✗), then the results are $$\begin{array}{c}{P}_1=Q_{1,3}=\{(2,1,2),(2,1,3),(3,1,2),(3,1,3)\}.\\ Q_{2,1}=Q_{2,2}=\{(2,1,2),(2,1,3)\}.\\ Q_{2,3}=P_2=\{(2,1,3)\}.\end{array}$$

Now, we describe the specific strategy.

Strategy 4. We, the codemaker, provide the feedback $\tau =({\tau }_1,{\tau }_2,\dots ,{\tau }_n)$ by the following method after receiving the guess x from the codebreaker in the i th round:

For τ₁, we search if there exists a word $a=(a_1,a_2,\dots ,a_n)\in P_{i-1}$ such that $a_1\ne x_1$. If such an a exists, set ${\tau }_1=$ ✗ and update the last answer set $Q_{i,1}$ to be those in $P_{i-1}$ whose first letter is not x₁. $Q_{i,1}$ is the possible answer set currently. Else, for every word $a\in P_{i-1}$, we have a₁ = x₁. Set ${\tau }_1=$ ✓and the lastest answer set $Q_{i,1}$ equals $P_{i-1}$.

Similarly, for ${\tau }_j,j\in \{2,3,\dots ,n\}$, we search to see if there exists word $a\in Q_{i,j-1}$ such that $a_j\ne x_j$. If such a word exists, set ${\tau }_j=$ ✗ and update the lastest answer set $$Q_{i,j}=\{a\in Q_{i,j-1}:a_j\ne x_j\}.$$

Else, set ${\tau }_j=$ ✓and update the lastest answer set $$Q_{i,j}=\{a\in Q_{i,j-1}:a_j=x_j\}=Q_{i,j-1}.$$

The feedback $\tau =({\tau }_1,{\tau }_2,\dots ,{\tau }_n)$ is produced.

Proposition 5.

If the codemaker provides feedback by using Strategy 4, the answer set will contain more than one word after k – 2 rounds, i.e., $\left|P_{k-2}\right|>1$.

Remark 6.

It can be inferred from Proposition 5 that there are at least two words to choose in the $(k-1)$st round, which means that any codebreaker cannot solve the puzzle in k – 1 rounds facing Strategy 4. Then we have $G(k)\ge k$. Consequently, Proposition 3 can be deduced from Proposition 5.

We are now going to prove Proposition 5. We first do some preparations.

We use a 0–1 matrix $A^{(r)}={(a_{\mathit{\text{ji}}}^{(r)})}_{k\times k}$ to track the codebreaker’s guesses and the codemaker’s feedback (tracking matrix for short) in the game after r rounds. It encodes the set P_r, as we will prove later, and is easier to handle.

We define the matrix recursively. Initially, the values in the matrix $A^{(0)}$ are all 1, which means $a_{\mathit{\text{ji}}}^{(0)}=1,\text{ for all }i,j\in [k]$. In the rth round, the codebreaker provides a guess $x=(x_1,x_2,\dots ,x_k)\in {[k]}^k$. Let us denote the feedback by $\tau =({\tau }_1,{\tau }_2,\dots ,{\tau }_k)\in {\{✓,✗\}}^k$. For each $i\in [k]$, if ${\tau }_i=$ ✗, then set $a_{x_i,i}^{(r)}$ as 0. Other elements in $A^{(r)}$ remain the same as the corresponding elements in $A^{(r-1)}$.

For example, when $k=n=4$, a codebreaker guessed (4,2,1,3), and the feedback is (✓,✓,✗,✗); the matrix $A^{(1)}$ is then

Table

letter position	1	2	3	4
1	1	1	0	1
2	1	1	1	1
3	1	1	1	0
4	1	1	1	1

We introduce the connections between $A^{(r)}$ and P_r.

Lemma 7.

If the codemaker provides feedback using Strategy 4, then for each permutation $\sigma \in S_k$, for all r < k, the word $y_0=(\sigma (1),\sigma (2),\dots ,\sigma (k))$ exists in the answer set P_r if and only if $$a_{\sigma (1),1}^{(r)}=a_{\sigma (2),2}^{(r)}=\dots =a_{\sigma (k),k}^{(r)}=1,$$where S_k is a symmetric group over all permutations of the numbers $1,2,\dots ,k,\sigma (i)$ is the ith value in σ, and $A^{(r)}={(a_{\mathit{\text{ji}}}^{(r)})}_{k\times k}$.

Proof.

It is trivial to see that every word $y=(\sigma (1),\sigma (2),\dots ,\sigma (k))$ in the answer set P_r maps to a permutation σ in S_k that satisfies $a_{\sigma (i),i}^{(r)}=1,\text{ for all }i\in [k]$. The rest is to prove the converse by using Strategy 4.

If $\sigma \in S_k,r\in \mathbb{N}$ satisfies that $a_{\sigma (i),i}^{(r)}=1,i=1,2,\dots ,k$, we are going to prove the word $y_0=(\sigma (1),\sigma (2),\dots ,\sigma (k))$ is in the answer set P_r. The answer set P₀ contains the word y₀ because the codemaker has not guessed.

We provide the proof by contradiction. If $y_0\notin P_r$, we assume that y₀ is removed from the answer set in the mth round ($m\le r$), which means $y_0\in P_{m-1}$ and $y_0\notin P_m$.

Let the guess and the feedback in the mth round be $x=(x_1,x_2,\dots ,x_n)$ and $\tau =({\tau }_1,{\tau }_2,\dots ,{\tau }_k)$, respectively. Since $$a_{\sigma (i),i}^{(r)}=1,i=1,2,\dots ,k,$$

we know that (2) $$a_{\sigma (i),i}^{(m)}=1,i=1,2,\dots ,k.$$(2)

Let $S=\{i\in [k]:x_i=\sigma (i)\}$, then from equation (2)(2) $$a_{\sigma (i),i}^{(m)}=1,i=1,2,\dots ,k.$$(2) , ${\tau }_i=$ ✓, $\text{ for all }i\in S$. For all $i\in [k]-S$, τ_i is ✗ according to Strategy 4. We know y₀ is still possible to be the answer word, which means $y_0\in P_m$. Contradiction! Thus $y_0\in P_r$. □

Intuitively, the lemma claims that $a_{j,i}^{(r)}=1$ means that y_i = j has not been eliminated as a possible solution after r rounds. Thus the product ${\prod }_{i=1}^k{a}_{\sigma (i),i}$ is 1 means that the permutation $\sigma =(\sigma (1),\sigma (2),\dots ,\sigma (k))$ is consistent with all responses so far and it is still possible to be the answer. We introduce the concept of the permanent of a matrix to better explain our proof.

The permanent of a square 0–1 matrix $A={(a_{\mathit{\text{ji}}})}_{k\times k}$ is defined as $$\mathrm{\text{perm}}(A)=\sum _{\sigma \in S_k}\prod _{i=1}^k{a}_{\sigma (i),i}.$$

In fact, if we define ${\mathcal{A}}_i=\{j:a_{\mathit{\text{ji}}}=1\}$, the permutation of A is the number of systems of distinct representatives of ${\mathcal{A}}_1,{\mathcal{A}}_2,\dots ,{\mathcal{A}}_k$ in the language of combinatorics.

The permanent counts the number of permutations σ such that the corresponding product ${\prod }_{i=1}^k{a}_{\sigma (i),i}$ equals 1. It can be deduced that the permanent of $A^{(r)}$ is the number of words in P_r. Thus our last goal is to prove that $\mathrm{\text{perm}}(A^{(k-2)})>1$ in order to prove Proposition 5.

Lemma 8.

Given a square 0–1 matrix A with a dimension of $k(k\ge 2)$, if A has a nonzero permanent and there are precisely two 1s in each of the columns, then the permanent of the matrix is larger than one.

Using Hall’s marriage theorem [10], it is easy to obtain Lemma 8. We provide another proof here.

Proof.

We use induction on k.

If k = 2, trivial.

Suppose that for $2\le k<k_0(k_0>2)$, the lemma holds. For k = k₀, either each row contains at least two 1s or there is at least a row with exactly one 1 because the permanent of the matrix is nonzero. Suppose that there are at least two 1s in each row, from the condition that each column has precisely two 1s, we obtain that each column has exactly two 1s.

Because the permanent of the matrix is nonzero, there is a permutation σ that satisfies $a_{\sigma (i),i}=1$ for each $i\in [k]$. We define σ₁ by ${\sigma }_1(i)\ne \sigma (i)$ is the position of the other 1 in the ith column for each $i\in [k]$. If there exists $i,j,b\in [k]$, such that $i\ne j$ and ${\sigma }_1(i)={\sigma }_1(j)=b$, from the fact that σ is a permutation we know that there exists the only l such that $\sigma (l)=b$. Additionally, from the definition of σ₁ we know $i\ne l,j\ne l$. Then the bth row has three 1s on the ith column, the jth column, and the lth column. Contradiction!

For all $i,j\in [k]$, if $i\ne j$, then ${\sigma }_1(i)\ne {\sigma }_1(j)$. It implies that σ₁ is a permutation, $\mathrm{\text{perm}}(A)\ge 2$.

Otherwise, we assume that in the jth row, there is only one 1. Assume that a_ji = 1, then $$\mathrm{\text{perm}}(A)=a_{\mathit{\text{ji}}}·\mathrm{\text{perm}}(A_0)=\mathrm{\text{perm}}(A_0),$$where A₀ is the submatrix formed by deleting the jth row and ith column of A, a square 0–1 matrix with a dimension of n – 1. By induction, $\mathrm{\text{perm}}(A)=\mathrm{\text{perm}}(A_0)\ge 2$. □

Corollary 9.

Given a square 0–1 matrix with a dimension of $k(k\ge 2)$, if the matrix has a nonzero permanent and there are at least two 1s in each column, then the permanent of the matrix is larger than one.

Finally, we provide the proof of Proposition 5.

Proof.

According to Strategy 4, each column of the tracking matrix $A^{(j)}$ has at least $(n-j)$ 1s and has a positive permanent after j rounds. Thus, after $(k-2)$ rounds, the tracking matrix $A^{(k-2)}$ satisfies the conditions in Corollary 9. The permanent of the matrix $A^{(k-2)}$ is larger than one, which means the answer set $P_{k-2}$ contains more than one word by Lemma 7. Thus Proposition 5 is proved. □

By Remark 6, Proposition 3 is proved. From the claim in the start of this section, the first case of Theorem 1 holds, i.e., $$F(k,n)=k,\text{ for all }k\le n.$$

2 The Second Case

For the case k > n and n divides k, we are going to prove $$F(k,n)=\frac{k}{n}+n-1.$$

Similar to the analysis in the first case, the codemaker only needs to provide feedback by using a specific strategy after each round and ensure that the answer set is not empty.

Lemma 10.

For Clear Mastermind with k positions, k letters, and the public information that the answer is a permutation of $\{1,2,\dots ,k\}$, if there exists $i,j\in \{1,2,\dots ,k\}$ such that the codebreaker knows the ith letter of the answer is not j, then the codebreaker can solve the puzzle within k – 1 rounds.

Proof.

Without loss of generality, we assume that $i=j=1$. Then, in the rth round when $r<k-1$, the codebreaker guesses $((r+1),r,r,\dots ,r)\in {[k]}^k$ until the first position of the feedback is Green. If it appears, the letter r + 1 won’t appear in other positions. The codebreaker can simply guess $((r+2),(r+2),\dots ,(r+2)),((r+3),(r+3),\dots ,(r+3))$ for the following rounds until the $(k-2)$th round. The answer set $P_{k-2}$ will contain only one word.

Otherwise, after k – 2 rounds, the answer set $P_{k-2}$ also contains only one word. Thus Lemma 10 holds. □

Next we prove that when k > n and n divides k, $$F(k,n)=\frac{k}{n}+n-1.$$

Proof.

On the one hand, in the initial $\frac{k}{n}-1$ rounds, the codemaker could provide feedback only containing Black because there are k kinds of letters in total and each guess contains n letters at most. Consequently, the best case for the codebreaker after $\frac{k}{n}-1$ rounds is equivalent to a Clear Mastermind game with n positions and n letters, which needs n more rounds to solve. Consequently, $$F(k,n)\ge \frac{k}{n}+n-1.$$

On the other hand, in the rth round when $r\le \frac{k}{n}$, the codebreaker could guess the word $((r-1)·n+1,(r-1)·n+2,\dots ,r·n)$. The codebreaker then knows all of the letters that appear in the answer after $\frac{k}{n}$ rounds.

If there are fewer than n kinds of letters appearing in the answer, the codebreaker needs no more than n – 1 rounds to solve the puzzle since $$F(m,n)\le m\le n-1,\text{ for all }m<n,$$according to the bound (1).

Otherwise, there are n kinds of letters appearing in the answer. From the initial $\frac{k}{n}$ guesses, we have obtained the letters appearing in the answer. If at least one Green appears in the feedback from the initial $\frac{k}{n}$ rounds, the codebreaker needs no more than $G(n-1)=n-1$ rounds to solve the puzzle. Otherwise, the feedback from the initial $\frac{k}{n}$ rounds has at least one Yellow. Then by Lemma 10, the codebreaker also needs n – 1 rounds to solve the puzzle. □

Above all, we prove that $$F(k,n)=\frac{k}{n}+n-1,\text{ when }k>n\text{ and }n\text{ divides }k$$

3 The Third Case and Future Work

Since $$F(k,n)\le F(k+1,n),\hspace{1em}\text{ for all }k,n\in {\mathbb{N}}^{*},$$and $$F(k,n)=\frac{k}{n}+n-1,\text{ when }k>n\text{ and }n\text{ divides }k$$ then the third case of Theorem 1 holds, i.e., $$\lfloor \frac{k}{n}\rfloor +n-1\le F(k,n)\le \lfloor \frac{k}{n}\rfloor +n,\text{ when }k>n\text{ and }n\text{ does not divide }k.$$

To obtain the exact result, we simulated the game using a computer program and obtained the results in Table 1 when $n<k<2n$. Denote by $\mathbf{N}$ the number of the words in the game with k letters and n positions, which is kⁿ. The complexity of the program is $O({\mathbf{N}}^2)$, making it challenging to compute $F(2n-1,n)$ when n > 5.

Table 1 Results of Clear Mastermind calculated by the computer when $n<k<2n$.

	$F(k,n)=n$	$F(k,n)=n+1$
n = 2		$F(3,2)=3$
n = 3	$F(4,3)=3$	$F(5,3)=4$
n = 4	$F(5,4)=F(6,4)=F(7,4)=4$
n = 5	$F(6,5)=F(7,5)=F(8,5)=F(9,5)=5$

We speculate that $$F(2n-1,n)=n,\text{ for all }n>3.$$

It doesn’t hold for smaller n. We suspect that the reason is when n is small, the feedback of Green provides little information about the other letters of the answer. For example, if the feedback contains two types of Green, representing whether the letter exists in other positions, we can verify that $F(3,2)=2\text{ and }F(5,3)=3$.

However, it is difficult to prove our speculation by simplifying the game as we did in the first case. In Section 1, we demonstrated that it is sufficient to prove $F(k,n)\ge k$ when $k\le n$, which means we need to prove the codebreaker cannot solve the Clear Mastermind with k letters and n positions in k – 1 rounds if $k\le n$. Thus we can make the Clear Mastermind easier to solve by providing the codebreaker with more information, which also helps us to show that the codebreaker still cannot win in k – 1 rounds. However, to prove $F(2n-1,n)=n,\text{ for all }n>3$, we need to prove $F(2n-1,n)<n+1,\text{ for all }n>3$ according to the third case of Theorem 1. One common approach is to make the game more difficult in some way that the codebreaker can still win in n rounds. This is more challenging than the former case.

Another potential extension that follows from our study is the relationship between $F(k+n,n)$ and F(k, n) when k > n and n does not divide k. It is trivial that $F(k+n,n)\ge F(k,n)+1$. However, we do not know whether the speculation $F(k+n,n)\le F(k,n)+1$ is true.

4 Conclusion

In this paper, we introduced Clear Mastermind, a combination of Mastermind and Wordle. We investigated the fewest number of guesses that a codebreaker required to find the answer in the game according to its two parameters: the number of letters and the length of the answer.

In the first case where $k\le n$, we simplified the game by switching the feedback, providing more information to the codebreaker, proposing a feedback strategy and introducing a tracking matrix. We found the fewest number of guesses required in the end.

In the second case where k > n and n divides k, the result is mainly based on the thoughts in the first case.

In the third case where k > n and n does not divide k, the result based on the first two cases is given. However, there is still further work to do.

Fig. 1 Illustration of two different instances of Clear MasterMind with n = 5 and k = 4.

Acknowledgment

The authors would like to thank their supervisor, Professor Liang Yu, for his insightful suggestions and encouragement. He pointed out some mistakes in a previous version of the paper and guided the authors to find another elegant and accurate proof. The authors also extend their sincere thanks to the anonymous referees for their constructive suggestions that led to a significant improvement of the paper.

Disclosure Statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

Renyuan Li

RENYUAN LI entered National University of Singapore in 2023, to pursue a Ph.D. in ISEM. Before that, he obtained his bachelor of science in statistics at Nanjing University.

Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 117576, Singapore

[email protected]

Shenglong Zhu

SHENGLONG ZHU received his bachelor of science in mathematics and applied mathematics from Nanjing University in 2023. He went on to pursue an academic master degree in mathematics at Nanjing University.

Mathematical Department, Nanjing University, Nanjing City, Jiangsu Province 210093, People’s Republic of China

[email protected]