Minesweeper on graphs |
| |
Authors: | Shahar Golan |
| |
Institution: | Department of Computer Science, Ben-Gurion University of the Negev, P.O. Box 653, Beer-Sheva 84105, Israel |
| |
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. |
| |
Keywords: | Minesweeper Counting problem Consistency Treewidth Constraint satisfaction CSP Generating polynomials Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|