How cellular automaton plays Minesweeper

摘要

The Windows Minesweeper game seems to be known to almost all who use personal computers. Mines are distributed inside the bounded room, and empty sites are filled with ciphers, indicating how many neighboring mines exist. At the start of a game we have all mines hidden and wish to mark them all. We construct a two-dimensional deterministic cellular automaton which marks all mines populated on the n × n size lattice in Ω(n) time. Every cell of this automaton has 25 closest neighbors including itself and 27 states.