On the algorithmic complexity of the Mastermind game with black-peg results |
| |
| Authors: | Michael T. Goodrich |
| |
| Affiliation: | 1. Dipartimento di Informatica Sistemistica e Comunicazione, Università degli Studi di Milano Bicocca, Viale Sarca 336, 20126 Milano, Italy;2. Dipartimento di Informatica, Università degli Studi di Salerno, via Giovanni Paolo II 132, 84084 Fisciano (SA), Italy;1. Max Planck Institute for Informatics, 66123 Saarbrücken, Germany;2. LIAFA, Université Paris Diderot - Paris 7, Paris, France;1. École Polytechnique, Palaiseau, France;2. Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, LIP6, Paris, France;3. CNRS, UMR 7606, LIP6, Paris, France;4. Saarland University, Saarbrücken, Germany;1. Technical University of Denmark, DTU Compute, Denmark;2. University of Warwick, Department of Computer Science, United Kingdom;1. Department of Computer Science, Technion, Haifa, 32000, Israel;2. Google, Mountain View, United States |
| |
| 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 Chvátal by almost a factor of 2. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
