On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results

Abstract

In this paper, we study the algorithmic complexity of the Mastermind game, where results are single-color black pegs. This differs from the usual dual-color version of the game, but better corresponds to applications in genetics. We show that it is NP-complete to determine if a sequence of single-color Mastermind results have a satisfying vector. We also show how to devise efficient algorithms for discovering a hidden vector through single-color queries. Indeed, our algorithm improves a previous method of Chvatal by almost a factor of 2.

Expanded version with a figure showing the Mastermind game

Cited by in corpus (7)

• Ranking-Based Black-Box Complexity
• Playing Mastermind with Many Colors
• The Worst Case Number of Questions in Generalized AB Game with and without White-peg Answers
• Learning Character Strings via Mastermind Queries, with a Case Study Involving mtDNA
• Hardness of Mastermind
• On the Query Complexity of Black-Peg AB-Mastermind
• Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies