umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
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, 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
Identifiers
URN: urn:nbn:se:umu:diva-82878DOI: 10.1016/j.ipl.2011.06.009ISI: 000295307300001OAI: oai:DiVA.org:umu-82878DiVA: diva2:663669
Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2017-12-06Bibliographically 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
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