Portal de Periódicos da CAPES

Mastermind is NP-Complete

2005; Volume: 5; Issue: 2 Linguagem: Inglês

1982-3363

Jeff Stuckman, Guo‐Qiang Zhang,

Computability, Logic, AI Algorithms

In this paper we show that the Mastermind Satisfiability Pro blem (MSP) is NP- complete. Mastermind is a popular game which can be turned into a logical puzzle called the Mastermind Satisfiability Problem in a similar spirit to the Minesweeper puzzle (5). By proving that MSP is NP-complete, we reveal its intrinsic computational property that makes it challenging and interesting. This serves as an addition to our knowledge about a host of other puzzles, such as Minesweeper (5), Mah-Jongg (1), and the 15-puzzle (6).