On the algorithmic complexity of the Mastermind game with black-peg results

DOI10.1016/J.IPL.2009.02.021zbMATH Open1197.91063OpenAlexW2045496672MaRDI QIDQ989451FDOQ989451

Michael T. Goodrich

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.02.021

Recommendations

• On the query complexity of black-peg AB-mastermind
• The number of pessimistic guesses in generalized black-peg mastermind
• The query complexity of a permutation-based variant of mastermind
• An optimal strategy for static black-peg Mastermind with two pegs
• Bounds for the static permutation mastermind game
• Query complexity of mastermind variants
• Game values and computational complexity: an analysis via black-white combinatorial games
• An optimal strategy for static black-peg mastermind with three pegs
• On the complexity of master problems

zbMATH Keywords

algorithmsNP-completenessmastermind

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Combinatorial games (91A46)

Cites Work

• Title not available (Why is that?)
• Mastermind
• Title not available (Why is that?)

Cited In (16)

• Title not available (Why is that?)
• The Query Complexity of Finding a Hidden Permutation
• Optimal schemes for combinatorial query problems with integer feedback
• Ranking-based black-box complexity
• Bounding memory for Mastermind might not make it harder
• On the query complexity of black-peg AB-mastermind
• Query complexity of mastermind variants
• The query complexity of a permutation-based variant of mastermind
• Playing Several Variants of Mastermind with Constant-Size Memory is not Harder than with Unbounded Memory
• The number of pessimistic guesses in generalized black-peg mastermind
• Playing mastermind with constant-size memory
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Mastermind with a linear number of queries
• The exact query complexity of yes-no permutation mastermind
• The worst case number of questions in generalized AB game with and without white-peg answers
• An Optimal Strategy for Static Black-Peg Mastermind with Two Pegs

This page was built for publication: On the algorithmic complexity of the Mastermind game with black-peg results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989451)