© Synapse Social LLC, 2026Privacy Policy

Pulse Explore Trending Questions Researchers

⌘K

Minesweeper as an NP-complete problem | Synapse

December 1, 2005

Minesweeper as an NP-complete problem

Key Points

The aim is to explain the NP-completeness of Minesweeper through engaging educational tools for students.
Developed a set of instructional slides
Presented solutions to two introductory Minesweeper puzzles
Simulated digital circuit elements to illustrate NP-completeness
Validated Minesweeper as NP-complete
Enhanced accessibility of complex computer science concepts for high school students
Provided a clear educational framework for demonstrating NP-completeness through practical examples

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.

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Loading...

Authors

M

Mordechai Ben‐Ari

Journals

ACM SIGCSE Bulletin

Actions

Institutions

Weizmann Institute of Science

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Loading...

Cite this study

Mordechai Ben‐Ari (Thu,) studied this question.

synapsesocial.com/papers/6980eea6b2861e37bf97a2a1 — DOI: https://doi.org/10.1145/1113847.1113873