The number of pessimistic guesses in Generalized Black-peg Mastermind
2011 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 111, no 19, 933-940 p.Article in journal (Refereed) Published
Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p; c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p; c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2; c), b(3; c) and b(4; c) and give upper and lower bounds for b(5; c) and a lower bound for b(6; c). Furthermore, for arbitrary p, we present upper bounds for b(p; 2), b(p; 3) and b(p; 4). Finally, we give bounds for the general case b(p; c). In particular, we improve an upper bound recently proved by Goodrich.
Place, publisher, year, edition, pages
Elsevier, 2011. Vol. 111, no 19, 933-940 p.
Combinatorial problems, Algorithms, Mastermind, Logic game, Computer aided proof
Discrete Mathematics Computer and Information Science
IdentifiersURN: urn:nbn:se:umu:diva-82878DOI: 10.1016/j.ipl.2011.06.009ISI: 000295307300001OAI: oai:DiVA.org:umu-82878DiVA: diva2:663669