umu.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
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, p. 933-940Article 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, p. 933-940
Keywords [en]
Combinatorial problems, Algorithms, Mastermind, Logic game, Computer aided proof
National Category
Discrete Mathematics Computer and Information Sciences
Identifiers
ISI: 000295307300001OAI: oai:DiVA.org:umu-82878DiVA, id: diva2:663669
Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2018-06-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Publisher's full text

Jäger, Gerold

Search in DiVA

Jäger, Gerold
In the same journal
Information Processing Letters
On the subject
Discrete MathematicsComputer and Information Sciences

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 79 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf