Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4630963 | Applied Mathematics and Computation | 2011 | 8 Pages |
Abstract
Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. In this paper, we present efficient algorithms for solving these problems for Minesweeper graphs with bounded treewidth. Our algorithms turn out to be much better than those based directly on dynamic programming. The algorithms mostly use of algebraic operations on multivariate polynomials, so that one may use existing software to implement them easily.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Shahar Golan,