El Ouali, Mourad and Sauerland, Volkmar (2013) Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation. Combinatorial Algorithms. IWOCA 2013. Lecture Notes in Computer Science, 8288 . pp. 443-447. DOI 10.1007/978-3-642-45278-9_40.

Full text not available from this repository.

Abstract

In the past three decades, deductive games have become interesting from the algorithmic point of view. Deductive games are two players zero sum games of imperfect information. The first player, called "codemaker", chooses a secret code and the second player, called "codebreaker", tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. A well known deductive game is the famous Mastermind game. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. 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 O(n log n) queries. Our algorithm improves the previous result of Ker-I Ko and Shia-Chung Teng (1985) 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. Keywords: Mastermind; combinatorial problems; permutations; algorithms

Document Type:	Article
Research affiliation:	Kiel University > Kiel Marine Science OceanRep > The Future Ocean - Cluster of Excellence
Refereed:	Yes
Open Access Journal?:	No
Publisher:	Springer
Projects:	Future Ocean
Date Deposited:	03 Apr 2018 09:51
Last Modified:	03 Nov 2023 13:44
URI:	https://oceanrep.geomar.de/id/eprint/42578

Actions (login required)

View Item