Abstract
In the past three decades, deductive games have become interesting from the algorithmic point of view. A well known deductive game is the famous Mastermind game. In this paper, we consider the so called Black-Peg variant of Mastermind. More precisely, we deal with a special version of the Black-Peg game with n holes and k ≥ n colors where no repetition of colors is allowed. We present a strategy that identifies the secret code in \(\mathcal{O}(n\log_2{n})\) queries. Our algorithm improves the previous result of Ker-I Ko and Shia-Chung Teng (1986) by almost a factor of 2 for the case k = n. To our knowledge there is no previous work dealing with the case k > n.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Chvátal, V.: Mastermind. Combinatorica 3, 325–329 (1983)
Doerr, B., Spöhel, R., Thomas, H., Winzen, C.: Playing Mastermind with Many Colors. In: Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 695–704. SIAM Society for Industrial and Applied Mathematics (2013)
Erdös, P., Rényi, C.: On Two Problems in Information Theory. Publications of the Mathematical Institute of the Hungarian Academy of Science 8, 229–242 (1963)
Goodrich, M.T.: On the algorithmic complexity of the Mastermind game with black-peg results. Information Processing Letters 109, 675–678 (2009)
Jäger, G., Peczarski, M.: The number of pessimistic guesses in generalized black-peg Mastermind. Information Processing Letters 111, 933–940 (2011)
Knuth, D.E.: The computer as a master mind. Journal of Recreational Mathematics 9, 1–5 (1977)
Ko, K., Teng, S.: On the Number of queries necessary to identify a permutation. Journal of Algorithms 7, 449–462 (1986)
Stuckman, J., Zhang, G.: Mastermind is \(\mathcal{NP}\)-complete. INFOCOMP Journal of Computer Science 5, 25–28 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
El Ouali, M., Sauerland, V. (2013). Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation. In: Lecroq, T., Mouchard, L. (eds) Combinatorial Algorithms. IWOCA 2013. Lecture Notes in Computer Science, vol 8288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45278-9_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-45278-9_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45277-2
Online ISBN: 978-3-642-45278-9
eBook Packages: Computer ScienceComputer Science (R0)