Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Richard Kaye's demonstration that a puzzle based on the Minesweeper game is NP-complete makes this important computer science topic accessible to high school students. The resource described here is a set of slides showing the detailed solution of two introductory puzzles, following by the step-by-step simulation of digital circuit elements required for proving NP-completeness.

REFERENCES

• 1: Kaye, R. (2000). Minesweeper is NP-complete. Mathematical Intelligencer 22(2), 9--15.
• 2: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
• 3: Stewart, I. (2005) Ian Stewart on Minesweeper. Clay Mathematics Institute,
• 4: http://www.claymath.org/Popular_Lectures/Minesweeper/
• 5: http://www.claymath.org/millennium/P_vs_NP/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Gaming

General Terms:
Algorithms, Design

Keywords:
NP-complete, SAT, minesweeper