minesweeper en · NOUN
Pronunciation
- /ˈmaɪnˌswipɚ/ (General-American)
- (US) audio
Etymology
From mine + sweeper.
Meanings
- (countable, uncountable) A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines).
- (countable, often, specifically, uncountable) A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines). ▸ A ship specializing in removing naval mines.
-
(uncountable) Any of various logic-based computer games in which the player has to discover the position of mines in a rectangular grid, based on numerical hints.
Information on the history of minesweeper and the rules of the game can be found on Wikipedia [14]. The book by Garey and Johnson [4] is the classical text on NP-completeness. Boolean satisfiability, SAT, is the original decision problem shown NP-complete by Cook [2]. […] Kaye [6] introduced minesweeper consistency and showed its NP-completeness through reduction from circuit-SAT. Kaye's circuit templates are quite involved. An and gate, for instance, has 23 × 13 squares and a wire crossing is built from and and not gates (24 in total). He later published some further, simplified templates [7), but they remain quite large. Kaye's reduction from circuit-SAT to minesweeper does not guarantee a predefined number of hidden mines. We re-establish the NP-completeness of minesweeper consistency by reduction from SAT for the original version of minesweeper with a given number of hidden mines. This illustrates that this extra piece of information does not fundamentally simplify minesweeper. The latter was also already observed by Scott et al. [8]. Scott et al. argue that Kaye's reasoning does not prove NP-completeness of playing minesweeper. Kaye assumed that minesweeper is played by iteratively solving minesweeper consistency. Scott et al. observe that there may be other strategies to play minesweeper. They therefore introduce the minesweeper inference problem, which precisely captures the essence of minesweeper game play. They show that minesweeper inference is co-NP-complete (and hence that playing minesweeper is most likely not NP-complete). They do so by reducing UNSAT to minesweeper inference, for the original version of minesweeper with a given number of hidden mines.
2022, Alex Thieme, Twan Basten, “Minesweeper is Difficult Indeed!: Technology Scaling for Minesweeper Circuits”, in Mariëlle Stoelinga, Nils Jansen, Petra van den Bos, editors, A Journey from Process Algebra Via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday [a festschrift], Springer Nature Switzerland, →ISBN, page 474:
Forms
| Spelling | Features | Labels | Source |
|---|---|---|---|
| minesweepers | Number=Plur | lexicographic |
Antonyms
Coordinates
Deriveds
Hypernyms
watercraft · vessel · vehicle · ship
Translations (62)
fr dragueur de mines (vehicle, device, or person for the removal of mines) · ro dragor (vehicle, device, or person for the removal of mines) · ko 소해정 (vehicle, device, or person for the removal of mines) · hu aknaszedő/aknamentesítő/aknakutató hajó (vehicle, device, or person for the removal of mines) · ja 掃海艦 (vehicle, device, or person for the removal of mines) · ko 소뢰정 (vehicle, device, or person for the removal of mines) · el ναρκαλιευτής (video game) · pl trałowiec (vehicle, device, or person for the removal of mines) · es buscaminas (vehicle, device, or person for the removal of mines) · th เรือกวาดทุ่นระเบิด (vehicle, device, or person for the removal of mines) · fr démineur (video game) · da minestryger (vehicle, device, or person for the removal of mines) · da minestryger (video game) · ru сапёр (video game) · fr démineur (vehicle, device, or person for the removal of mines) · cmn 掃雷 /扫雷 (video game) · is sprengjuleit (vehicle, device, or person for the removal of mines) · sv minsvepare (vehicle, device, or person for the removal of mines) · ko 소해함 (vehicle, device, or person for the removal of mines) · fi miinaharava (vehicle, device, or person for the removal of mines) · ko 지뢰 찾기 (video game) · it campo minato (video game) · fi miinanraivaaja (vehicle, device, or person for the removal of mines) · ka ტრალერი (vehicle, device, or person for the removal of mines) · fi miinaharava (video game) · sv minröjare (vehicle, device, or person for the removal of mines) · it dragamine (vehicle, device, or person for the removal of mines) · ca pescamines (video game) · nl mijnenveger (video game) · vi dò mìn (video game) · pl saper (vehicle, device, or person for the removal of mines) · ja 掃海艇 (vehicle, device, or person for the removal of mines) · ar كانسة الألغام (video game) · it sminatore (vehicle, device, or person for the removal of mines) · sk míny (video game) · tr mayın tarlası (video game) · no minesveipar (1, 2) (vehicle, device, or person for the removal of mines) · ca dragamines m. (vehicle, device, or person for the removal of mines) · ca caçamines (vehicle, device, or person for the removal of mines) · cs minolovka (vehicle, device, or person for the removal of mines) · pt campo minado (video game) · de Minenräumboot (vehicle, device, or person for the removal of mines) · cs hledání min (video game) · el ναρκαλιευτής (vehicle, device, or person for the removal of mines) · hu aknászhajó (vehicle, device, or person for the removal of mines) · es buscaminas (video game) · ru сапёр (vehicle, device, or person for the removal of mines) · cmn 掃雷艦 /扫雷舰 (vehicle, device, or person for the removal of mines) · es barreminas (vehicle, device, or person for the removal of mines) · ru ми́нный трал, тра́льщик (vehicle, device, or person for the removal of mines) · ca pescamines (vehicle, device, or person for the removal of mines) · nl mijnenveger (vehicle, device, or person for the removal of mines) · de Minesweeper (video game) · de Minenabwehrfahrzeug (vehicle, device, or person for the removal of mines) · ko 소해선 (vehicle, device, or person for the removal of mines) · ja マインスイーパー (video game) · sv minröj (video game) · hu aknakereső (video game) · ro deminor (vehicle, device, or person for the removal of mines) · ka გამნაღმავი ხომალდი (vehicle, device, or person for the removal of mines) · es dragaminas (vehicle, device, or person for the removal of mines) · pl saper (video game)