‘Minesweeper’ and spectrum of discrete Laplacians

Abstract

The article is devoted to a problem inspired by the ‘Minesweeper’ computer game. It is shown that certain configurations of open cells guarantee the existence and the uniqueness of solution. Mathematically the problem is reduced to some spectral properties of discrete differential operators. It is shown how the uniqueness can be used to create a new game which preserves the spirit of ‘Minesweeper’ but does not require a computer.

Keywords:

• Minesweeper
• paper minesweeper
• spectrum of discrete Laplacians

AMS Subject Classifications::

• 46N99
• 47N99
• 68R99

Acknowledgements

This research was done in frames of the EECM project of the mathematical department of the university of Aveiro. This work was done during the visit of Oleg German to Aveiro, Portugal. He thanks the CEOC research unity for warm hospitality. After the release of the first version of the paper E.L. had most fruitful discussions with Alexander Klimov, Dmitry Yarotsky and Vladimir Viro. He is also grateful to Profs Laszlo Erdös, Yakov Sinai, Boris Vainberg for the opportunity of giving a talk on this subject at their seminars. This research was supported by RFBR (grant No 06–01–00518) grant of the President of Russian Federation No MK–4466.2008.1. Centre for Research on Optimization and Control (CEOC) from the ‘Fundação para a Ciência e a Tecnologia’ (FCT), cofinanced by the European Community Fund FEDER/POCTI and by FCT research projects PTDC/MAT/72840/2006, PTDC/MAT/103197/2008.

Notes

Notes

1. for the game it is supposed that V has a certain graphical representation, such that each vertex represents a cell in which either a ‘mine’ or a number can potentially be located.

2. Special thanks to Professor Ana Breda for organization of this project.