Hyperbolic Minesweeper is in P
arXiv:2002.09534 · doi:10.4230/LIPIcs.FUN.2021.18
Abstract
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
arXiv commentfixed an error in Corollary 5.6: planar graph -> (r,d)-hyperbolic graph