Editing Mastermind (board game) (section)

===Complexity and the satisfiability problem===

In November 2004, Michiel de Bondt proved that solving a ''Mastermind'' board is an [[NP-complete]] problem when played with ''n'' pegs per row and two colors, by showing how to represent any [[one-in-three 3SAT]] problem in it. He also showed the same for ''Consistent Mastermind'' (playing the game so that every guess is a candidate for the secret code that is consistent with the hints in the previous guesses).<ref>{{citation
|last=De Bondt
|first=Michiel C.
|title=NP-completeness of Master Mind and Minesweeper
|publisher=Radboud University Nijmegen
|date=November 2004
|url=http://www.math.ru.nl/onderzoek/reports/rep2004/rep04_18.ps.gz
}}</ref>{{better source needed|reason=This is a compressed pdf file on a university server. As such it is effectively self-published as per WP:RS/SPS.|date=August 2021}}

The ''Mastermind satisfiability problem'' (MSP) is a [[decision problem]] that asks, "Given a set of guesses and the number of colored and white key pegs scored for each guess, is there at least one secret pattern that generates those exact scores?"  (If not, then the codemaker must have incorrectly scored at least one guess.) In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an [[arXiv]] article that MSP is NP-complete.<ref>{{Cite arXiv| title=Mastermind is NP-Complete | date=13 December 2005 | first1=Guo-Qiang | last1=Zhang | last2=Stuckman | first2=Geoff| eprint=cs.CC/0512049 }}</ref>{{better source needed|reason=This is a preprint, which means it is not a reliable source as per WP:PREPRINTS.|date=August 2021}}