link

October 29, Wednesday
12:00 – 13:30

Minesweeper on graphs
Graduate seminar
Lecturer : Mr. Shahar Golan
Lecturer homepage : http://www.cs.bgu.ac.il/faculty/person/golansha.html
Affiliation : CS, BGU
Location : 202/37
Host : Graduate Seminar
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. We present a polynomial algorithm for solving these problems for minesweeper graphs with bounded tree width. There is a close connection between the minesweeper problems and general CSP problems.