let a computer program be given as input the location of all mines and a list of squares which have already been revealed, with their revealed numbers. program produces, as quickly as possible, a sequence of absolutely safe moves which solve the grid exactly as far as safely possible. it might not completely solve the grid. for every unrevealed square at the end, the program also produces a complete hypothetical minesweeper grid has a bomb at that location and is otherwise consistent (minesweeper consistency problem, MCP) with revealed knowledge at the end.
MCP is NP-complete, so there are probably plenty of opportunities for programmers to develop clever heuristics to improve performance, similar to SAT and SMP solver competitions.
checking a program's steps is tedious and requires a known-correct (not necessarily fast) MCP solver. for every move, check that a counterfactual bomb (mine) at that location is inconsistent with the state of revealed knowledge at that point.
(the same routine could be used to punish guessing in a conventional minesweeper game for humans.)
are random minesweeper grids likely to have difficult situations in them? if so, what should the density of mines be? what, and how much, should be revealed? should the total number of mines be given?
No comments :
Post a Comment