3 citations · 5 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2012★ 3 cited
The computational complexity of Minesweeper
Michiel de Bondt
We show that the Minesweeper game is PP-hard, when the object is to locate all mines with the highest probability. When the probability of locating all mines may be infinitesimal,…
cs.CC2012★ 2 cited
Solving Mahjong Solitaire boards with peeking
Michiel de Bondt
We first prove that solving Mahjong Solitaire boards with peeking is NP-complete, even if one only allows isolated stacks of the forms /aab/ and /abb/. We subsequently show that la…