The worst case number of questions in Generalized AB game with and without white-peg answers

Discrete Applied Mathematics - Tập 184 - Trang 20-31 - 2015
Gerold Jäger1, Marcin Peczarski2
1Department of Mathematics and Mathematical Statistics, University of Umeå, SE-901-87 Umeå, Sweden
2Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland

Tài liệu tham khảo

Chen, 2004, Optimal algorithms for 2×n AB games—a graph-partition approach, J. Inf. Sci. Eng., 20, 105 Chen, 2004, Optimal algorithms for 2×n mastermind games—a graph-partition approach, Comput. J., 47, 602, 10.1093/comjnl/47.5.602 Chen, 2007, A two-phase optimization algorithm for mastermind, Comput. J., 50, 435, 10.1093/comjnl/bxm006 Chvátal, 1983, Mastermind, Combinatorica, 3, 325, 10.1007/BF02579188 Doerr, 2013, Playing mastermind with many colors, 695 Doerr, 2012, Playing mastermind with constant-size memory, vol. 14, 441 El Ouali, 2013, Improved approximation algorithm for the number of queries necessary to identify a permutation, vol. 8288, 443 Focardi, 2012, Guessing bank PINs by winning a mastermind game, Theory Comput. Syst. (MST), 50, 52, 10.1007/s00224-011-9340-9 Gagneur, 2011, Selective phenotyping, entropy reduction and the mastermind game, BMC Bioinformatics (BMCBI), 12, 406, 10.1186/1471-2105-12-406 Goddard, 2003, Static mastermind, J. Combin. Math. Combin. Comput., 47, 225 Goodrich, 2009, On the algorithmic complexity of the mastermind game with black-peg results, Inform. Process. Lett., 109, 675, 10.1016/j.ipl.2009.02.021 Guervós, 2011, Improving and scaling evolutionary approaches to the mastermind problem, vol. 6624, 103 Huang, 2010, Optimal analyses for 3×n AB games in the worst case, vol. 6048, 170 Jäger, 2009, The number of pessimistic guesses in generalized mastermind, Inform. Process. Lett., 109, 635, 10.1016/j.ipl.2009.02.016 Jäger, 2011, The number of pessimistic guesses in generalized black-peg mastermind, Inform. Process. Lett., 111, 933, 10.1016/j.ipl.2011.06.009 Knuth, 1976, The computer as mastermind, J. Recreat. Math., 9, 1 Ko, 1986, On the number of queries necessary to identify a permutation, J. Algorithms, 7, 449, 10.1016/0196-6774(86)90013-1 Koyama, 1993, An optimal mastermind strategy, J. Recreat. Math., 25, 251 McKay, 1998, Isomorph-free exhaustive generation, J. Algorithms, 26, 306, 10.1006/jagm.1997.0898 Source code of this article. Available: http://mimuw.edu.pl/~marpe/research/src/abgame.zip. Stuckman, 2006, Mastermind is NP-complete, INFOCOMP J. Comput. Sci., 5, 25 Viglietta, 2012, Hardness of mastermind, vol. 7288, 368