2013/03/23 by Mourad El Ouali, Ouali, Mourad El, Volkmar Sauerland +1
Computer Science · Engineering · #Algorithms and Data Compression #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1303.5862
openalex publication_date 2013/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the past three decades, deductive games have become interesting from the\nalgorithmic point of view. Deductive games are two players zero sum games of\nimperfect information. The first player, called "codemaker", chooses a secret\ncode and the second player, called "codebreaker", tries to break the secret\ncode by making as few guesses as possible, exploiting information that is given\nby the codemaker after each guess. A well known deductive game is the famous\nMastermind game. In this paper, we consider the so called Black-Peg variant of\nMastermind, where the only information concerning a guess is the number of\npositions in which the guess coincides with the secret code. More precisely, we\ndeal with a special version of the Black-Peg game with n holes and k >= n\ncolors where no repetition of colors is allowed. We present a strategy that\nidentifies the secret code in O(n log n) queries. Our algorithm improves the\nprevious result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2\nfor the case k = n. To our knowledge there is no previous work dealing with the\ncase k > n.\n Keywords: Mastermind; combinatorial problems; permutations; algorithms\n