On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results
| dc.creator | Goodrich, Michael T. | |
| dc.date | 2009-04-30 | |
| dc.date.accessioned | 2026-07-07T13:13:57Z | |
| dc.date.available | 2026-07-07T13:13:57Z | |
| dc.description | 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. | |
| dc.description | Expanded version with a figure showing the Mastermind game | |
| dc.identifier | https://arxiv.org/abs/0904.4911 | |
| dc.identifier | http://arxiv.org/abs/0904.4911 | |
| dc.identifier | Information Processing Letters, Volume 109, 675-678, 2009 | |
| dc.identifier | doi:10.1016/j.ipl.2009.02.021 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230062 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.title | On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results | |
| dc.type | text |