Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?

In the permutation Mastermind game, the goal is to uncover a secret permutation σ^⋆: n → n by making a series of guesses π₁, …, πT which must also be permutations of n, and receiving as feedback after guess πₜ the number of positions i for which σ^⋆ (i) = πₜ (i). While the existing literature on permutation Mastermind suggests strategies in which πₜ and πₓ+₁ might be widely different permutations, a resurgence in popularity of this game as a TikTok trend shows that humans (or at least TikTok influencers) use strategies in which consecutive guesses are very similar. For example, it is common to see players attempt one transposition at a time and slowly see their score increase. Motivated by these observations, we study the theoretical impact of two forms of locality in permutation Mastermind strategies: 𝓁ₖ-local strategies, in which any two consecutive guesses differ in at most k positions, and the even more restrictive class of wₖ-local strategies, in which consecutive guesses differ in a window of length at most k. We show that, in broad terms, the optimal number of guesses for local strategies is quadratic, and thus much worse than the O (n lg n) guesses that suffice for non-local strategies. We also show NP-hardness of the satisfiability version for 𝓁₃-local strategies, whereas in the 𝓁₂-local variant the problem admits a randomized polynomial-time algorithm.