Change search
ReferencesLink to record
Permanent link

Direct link
The number of pessimistic guesses in Generalized Black-peg Mastermind
Institute for Applied Stochastics and Operations Research, Technical University of Clausthal, D-38678 Clausthal, Germany.
Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
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
Abstract [en]

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.
Keyword [en]
Combinatorial problems, Algorithms, Mastermind, Logic game, Computer aided proof
National Category
Discrete Mathematics Computer and Information Science
URN: urn:nbn:se:umu:diva-82878DOI: 10.1016/j.ipl.2011.06.009ISI: 000295307300001OAI: diva2:663669
Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2013-11-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
In the same journal
Information Processing Letters
Discrete MathematicsComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 49 hits
ReferencesLink to record
Permanent link

Direct link