Minesweeper (video game)

Minesweeper is a puzzle video game genre. In the game, mines (that resemble naval mines in the classic theme) are scattered throughout a board, which is divided into cells. Cells have three states: unopened, opened, and flagged. An unopened cell is blank and clickable, while an opened cell is exposed. Flagged cells are those marked by the player to indicate a potential mine location. Objective and strategy A game of Minesweeper begins when the player first selects a cell on a board. In some variants the first click is guaranteed to be safe, and some further guarantee that all adjacent cells are safe as well. During the game, the player uses information given from the opened cells to deduce further cells that are safe to open, iteratively gaining more information to solve the board. The player is also given the number of remaining mines in the board, known as the minecount, which is calculated as the total number of mines subtracted by the number of flagged cells (thus the minecount can be negative if too many flags have been placed). To win a game of Minesweeper, all non-mine cells must be opened without opening a mine. There is no score, but there is a timer recording the time taken to finish the game. Difficulty can be increased by adding mines or starting with a larger grid. Most variants of Minesweeper that are not played on a fixed board offer three default board configurations, usually known as Beginner, Intermediate, and Expert, in order of increasing difficulty. Beginner is usually on an 8x8 or 9x9 board containing 10 mines, Intermediate is usually on a 16x16 board with 40 mines and Expert is usually on a 30x16 board with 99 mines; however, there is usually an option to customise board size and mine count. File:Minesweeper 9x9_10 example 1.png File:Minesweeper 9x9_10 example 2.png File:Minesweeper 9x9_10 example 4.png File:Minesweeper 9x9_10 example 7.png File:Minesweeper 9x9_10 example 9.png File:Minesweeper 9x9_10 example 11.png File:Minesweeper 9x9_10 example 13.png File:Minesweeper 9x9_10 example 15.png File:Minesweeper 9x9_10 example 16.png ==History==

According to TechRadar, Minesweeper was created by Microsoft in the 1990s, but Eurogamer commented that Minesweeper gained a lot of inspiration from a "lesser known, tightly designed game", Mined-Out by Ian Andrew for the ZX Spectrum in 1983. According to Andrew, Microsoft copied Mined-Out for Microsoft Minesweeper. A later version, found present in Windows Vista's Minesweeper, offered a tileset with flowers replacing mines as a response. The game is frequently bundled with operating systems and desktop environments, including Minesweeper for IBM's OS/2, Microsoft Windows, KDE, GNOME and Palm OS. Microsoft Minesweeper was included by default in Windows until Windows 8 (2012). Microsoft replaced this with a free-to-play version of the game, downloadable from the Microsoft Store. ==Variants==

Variants of Minesweeper have been made that expand on the basic concepts and add new game design elements. Minesweeper X is a clone of the Microsoft version with improved randomization and more statistics, and is another clone of the Microsoft version available as a mobile and tablet app for iOS users. It includes quick flagging and quick open mode. Users also have the option to change their board appearance from the classic gray/mines to flowers or clouds. Because this version is limited to use on mobile and iPad, it may not be ideal for players aiming to reach a fast time. Minesweeper was made part of RuneScape through a minigame called Vinesweeper. The video game Minecraft released a version of Minesweeper in its 2015 April Fools' Day update called Minescreeper. The HP-48G graphing calculator includes a variant called "Minehunt", where the player has to move safely from one corner of the playfield to the other. The only clues given are how many mines are in the squares surrounding the player's current position. Google Search includes a version of Minesweeper, available by searching the game's name. A logic puzzle variant of Minesweeper, suitable for playing on paper, starts with some squares already revealed. The player cannot reveal any more squares, but must instead mark the remaining mines correctly. Unlike the usual form of Minesweeper, these puzzles usually have a unique solution. These puzzles appeared under the name "tentaizu" (天体図), Japanese for a star map, in Southwest Airlines' magazine Spirit in 2008–2009. File:Tentaizu puzzle.png|A tentaizu puzzle File:Minesweeper games2relaxnet.png|Online, non-rectangular File:Cube Minesweeper 3D.png|3D File:Firefox Hexagon Minesweeper - fr.png|Hexagonal File:Xbomb triangles.png|Triangular File:Firefox Multiple mines.png|Multiple mines in cells File:Emoji Minesweeper.png|Emoji minesweeper == Competitive play ==

Competitive Minesweeper players aim to complete the game as fast as possible. The players memorize patterns to reduce times. Other players do not flag mines at all. A community of dedicated players has emerged; this community was centralized on websites such as Minesweeper.info.'' ==Computational complexity==

In 2000, Sadie Kaye published a proof that Minesweeper is NP-complete to determine whether a given grid of uncovered, correctly flagged, and unknown squares, the labels of the foremost also given, has an arrangement of mines for which it is possible within the rules of the game. The argument is constructive, a method to quickly convert any Boolean circuit into such a grid that is possible if and only if the circuit is satisfiable; membership in NP is established by using the arrangement of mines as a certificate. If, however, a minesweeper board is already guaranteed to be consistent, solving it is not known to be NP-complete, but it has been proven to be co-NP-complete. In the latter case, however, minesweeper exhibits a phase transition analogous to -SAT: when more than 25% of squares are mines, solving a board requires guessing an exponentially-unlikely set of mines. Kaye also proved that infinite Minesweeper is Turing-complete. ==See also==