Minesweeper (video game): Difference between revisions
AsceticRose (talk | contribs) m Reverted 1 edit by Thelord238 identified as test/vandalism using STiki |
m Made co-NP-complete a link. |
||
Line 47: | Line 47: | ||
==Computational complexity== |
==Computational complexity== |
||
In 2000, Richard Kaye published a proof that it 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 [[Circuit satisfiability problem|satisfiable]]; membership in NP is established by using the arrangement of mines as a certificate.<ref name="Kaye00">Kaye (2000)</ref> If, however, a minesweeper board is already guaranteed to be consistent, solving it is not known to be NP-complete, but interestingly it has been proven to be co-NP-complete.<ref>Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, ''The Mathematical Intelligencer'' '''33''':4 (2011), pp. 5-17.</ref> |
In 2000, Richard Kaye published a proof that it 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 [[Circuit satisfiability problem|satisfiable]]; membership in NP is established by using the arrangement of mines as a certificate.<ref name="Kaye00">Kaye (2000)</ref> If, however, a minesweeper board is already guaranteed to be consistent, solving it is not known to be NP-complete, but interestingly it has been proven to be [[co-NP-complete]].<ref>Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, ''The Mathematical Intelligencer'' '''33''':4 (2011), pp. 5-17.</ref> |
||
==Measuring board difficulty== |
==Measuring board difficulty== |
Revision as of 00:36, 10 August 2014
Minesweeper is a single-player puzzle video game. The objective of the game is to clear a rectangular board containing hidden "mines" without detonating any of them, with help from clues about number of neighboring mines in each field. The game originates from the 1960s, and has been written for many computing platforms in use today. It has many variations and offshoots.
Overview
The player is initially presented with a grid of undifferentiated squares. Some randomly selected squares, unknown to the player, are designated to contain mines. Typically, the size of the grid and the number of mines are set in advance by the user, either by entering the numbers or selecting from defined skill levels, depending on the implementation.
The game is played by revealing squares of the grid by clicking or otherwise indicating each square. If a square containing a mine is revealed, the player loses the game. If no mine is revealed, a digit is instead displayed in the square, indicating how many adjacent squares contain mines; if no mines are adjacent, the square becomes blank. The player uses this information to deduce the contents of other squares, and may either safely reveal each square or mark the square as containing a mine.
In some versions, a question mark may be placed in an unrevealed square to serve as an aid to logical deduction. Implementations may also allow players to quickly "clear around" a revealed square once the correct number of mines have been flagged around it. The game is won when all mine-free squares are revealed, because all mines have been located.
Some versions of Minesweeper will set up the board by never placing a mine on the first square revealed, or by arranging the board so that the solution does not require guessing.[citation needed] Minesweeper for versions of Windows protects the first square revealed; in Windows 7, players may elect to replay a board, in which case the first square may no longer be protected.
History
Minesweeper has its origins in the earliest mainframe games of the 1960s and 1970s. The earliest ancestor of Minesweeper was Jerimac Ratliff's Cube. The basic gameplay style became a popular segment of the puzzle game genre during the 1980s, with such titles as Mined-Out (Quicksilva, 1983), Yomp (Virgin Interactive, 1983), and Cube. Cube was succeeded by Relentless Logic (or RLogic for short), by Conway, Hong, and Smith, available for MS-DOS as early as 1985; the player took the role of a private in the United States Marine Corps, delivering an important message to the U.S. Command Center. RLogic had greater similarity to Minesweeper than to Cube in concept, but a number of differences exist:
- In RLogic, the player must navigate through the minefield, from the top left right angled corner to the bottom right right angled corner (the Command Center).
- It is not necessary to clear all non-mine squares. Also, there is no mechanism for marking mines or counting the number of mines found.
- The number of steps taken is counted. Although no high score functionality is included, players could attempt to beat their personal best score for a given number of mines.
- Unlike Minesweeper, the size of the minefield is fixed. However, the player may still specify the number of mines.
- Because the player must navigate through the minefield, it is sometimes impossible to win — namely, when the mines block all possible paths.
The gameplay mechanics of Minesweeper are included in a variety of other software titles, including:
- The mini-game Vinesweeper implemented into the MMORPG RuneScape; in this iteration (written by Jagex developer Danny J), the Minesweeper gameplay is given a large multiplayer aspect and the "game board" adopts a continually resetting timer. This allows for a never-ending game of Minesweeper where the skill is awarded assessed in points rather than "game completion".
- The PC game Mole Control (developed by Remode); in this game, the minesweeper mechanic is integrated into a puzzle adventure game based in a village called Molar Creek, which has been overrun with exploding moles. You play the local inventor's assistant, who is tasked with clearing the village of exploding moles, and you can also take part in the Molar Creek Annual Mole Control competition in a Time Attack Mode.
Distribution and variants
Versions of Minesweeper are frequently bundled with operating systems and GUIs, including Minesweeper for OS/2, Minesweeper in Windows, KMines in KDE (Unix-like OSes), Gnomine in GNOME and MineHunt in Palm OS. Many clones can be found on the Internet.
Variants of the basic game generally have differently shaped minefields, in either two and three dimensions, and may have more than one mine per cell. For example, X11-based XBomb adds triangular and hexagonal grids, and Professional Minesweeper for Windows includes these and others.
The HP-48G graphing calculator includes a variation on the theme 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.
A minigame in FIFA 11 is a variation of Minesweeper.[citation needed]
The Voltorb Flip game in the non-Japanese releases of Pokemon HeartGold and SoulSilver is a variation of Minesweeper and Picross.
The Coincentration minigame in Super Mario 64 DS and New Super Mario Bros. is similar to Minesweeper.
Another derivative of Minesweeper is Tentaizu, which could be described as a Minesweeper with some squares initially revealed, where the player doesn't reveal any squares, only mark them, and whose objective is to mark all mines correctly. Tentaizu puzzles usually have a unique solution.
-
Online, non rectangular
-
3D
-
hexagonal
-
triangular
-
Many mines in some cells
Computational complexity
In 2000, Richard Kaye published a proof that it 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.[1] If, however, a minesweeper board is already guaranteed to be consistent, solving it is not known to be NP-complete, but interestingly it has been proven to be co-NP-complete.[2]
Measuring board difficulty
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Kmines_3BV_8.png/220px-Kmines_3BV_8.png)
The difficulty of a given minesweeper board is often measured using the 3BV measure (stands for Bechtel's Board Benchmark Value).
Method
The 3BV of a board is the total count of:
- openings of the board, i.e. regions of orthogonally or diagonally contiguous squares having no neighbouring mines, together with the immediately surrounding numbered squares
- numbered squares that are not part of any openings.
For example, in the illustrated example, there is one opening (shown by white borders) and there are seven further numbered squares (green dots), giving a 3BV rating of 8. Equivalently, it is the minimum number of single clicks required in typical implementations to reveal all of the mine-free squares.
3BV/s
3BV/s stands for 3BV per second.
Because the time that is needed to finish a Minesweeper board depends highly on the difficulty of the board, it may not be the best way to compare records. 3BV/s on the other hand does consider the difficulty of the Minesweeper board as well as the time needed to finish it. Among the best Minesweeper players, 3BV/s records are not nearly as important as time records, but they give a picture of how fast someone can play with regard to mouse-handling.
If flags are marked, it is possible to require fewer clicks than the 3BV of the respective board. Using only left clicks is called non-flagging (nf) whereas marking mines with right-clicks is called flagging-style.
Criticism
Created by Ubisoft In 2001, the Italian "International Campaign to Ban Winmine" voiced strong concern over the game, contending that it is an "offense against the victims of the mines" and those who risk their lives to clear them. They created their own "Winflower" game, and lobbied Microsoft to use it in place of Minesweeper in Windows 98.[3] As a reaction to this criticism, the version of Minesweeper included in Windows Vista and Windows 7 offers a mode in which the mines are replaced with flowers.[4]
See also
Trivia
Commonly, the color code for the numbers is blue for 1, green for 2, red for 3, purple or dark blue for 4, maroon for 5, cyan for 6, black for 7, and grey for 8.
Notes
- ^ Kaye (2000)
- ^ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5-17.
- ^ Blincoe (2001)
- ^ Template:Wayback
References
- Adamatzky, Andrew (1997). "How cellular automaton plays Minesweeper". Applied Mathematics and Computation. 85 (2–3): 127–137. doi:10.1016/S0096-3003(96)00117-8.
- Lakshtanov, Evgeny; Oleg German (2010). "'Minesweeper' and spectrum of discrete Laplacians". Applicable analysis. 89 (12): 1907–1916. doi:10.1080/00036811.2010.505189.
- Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367. Further information available online at Richard Kaye's Minesweeper pages.
- Blincoe, Robert (21 June 2001). "Windows Minesweeper is an 'offence to mine victims'". The Register. Situation Publishing Ltd. Retrieved 5 May 2009.
External links
- Constraint Processing Techniques for Minesweeper
- [1] - Article by a lecturer in pure mathematics.
- Minesweeper at Curlie