minesweeper
Part of speech: noun
Morphological type: compound
Topics: computing
engineering
mathematics
natural-sciences
physical-sciences
sciences
video-games
Etymology: From mine + sweeper.
Compound parts: mine
sweeper
Inflected forms:
form: minesweepers
pos: noun
tags: plural
Senses:
gloss: A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines).
pos: noun
tags: countable
uncountable
gloss: A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines).
pos: noun
tags: countable
often
specifically
uncountable
gloss: 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.
pos: noun
tags: uncountable
examples: 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.
Derived words: destroyer minesweeper
Translations:
lang: Catalan
word: caçamines
lang: Catalan
word: dragamines m.
lang: Catalan
word: pescamines
lang: Chinese Mandarin
word: 掃雷艦 /扫雷舰
roman: sǎoléijiàn
lang: Czech
word: minolovka
lang: Danish
word: minestryger
lang: Dutch
word: mijnenveger
lang: Finnish
word: miinaharava
lang: Finnish
word: miinanraivaaja
lang: French
word: démineur
lang: French
word: dragueur de mines
lang: Georgian
word: ტრალერი
roman: ṭraleri
lang: Georgian
word: გამნაღმავი ხომალდი
roman: gamnaɣmavi xomaldi
lang: German
word: Minenabwehrfahrzeug
lang: German
word: Minenräumboot
lang: Greek
word: ναρκαλιευτής
roman: narkalieftís
lang: Hungarian
word: aknaszedő/aknamentesítő/aknakutató hajó
lang: Hungarian
word: aknászhajó
lang: Icelandic
word: sprengjuleit
lang: Italian
word: sminatore
lang: Italian
word: dragamine
lang: Japanese
word: 掃海艇
roman: sōkaitei
lang: Japanese
word: 掃海艦
roman: sōkaikan
lang: Korean
word: 소해정
roman: sohaejeong
lang: Korean
word: 소뢰정
roman: soroejeong
lang: Korean
word: 소해선
roman: sohaeseon
lang: Korean
word: 소해함
roman: sohaeham
lang: Norwegian
word: minesveipar (1, 2)
lang: Polish
word: saper
lang: Polish
word: trałowiec
lang: Romanian
word: dragor
lang: Romanian
word: deminor
lang: Russian
word: ми́нный трал, тра́льщик
roman: mínnyj tral, trálʹščik
lang: Russian
word: сапёр
roman: sapjór
lang: Spanish
word: dragaminas
lang: Spanish
word: barreminas
lang: Spanish
word: buscaminas
lang: Swedish
word: minsvepare
lang: Swedish
word: minröjare