Проблема выполняемости линейной карты для игр «Сапер» и «Цветной сапер»

Abstract

В работе рассматривается игра «Сапер» и ее модификация «Цветной сапер», в которой все закрытые клетки разбиты на классы, а расстановка чисел на открытых клетках является частичной. Доказано, что проблема выполняемости карты ограниченной ширины L для игр «Сапер» и «Цветной сапер» разрешима за полиноминальное время L ϵ N и L = 1 соответственно. Показано, что при L>1 данная проблема для игры «Цветной сапер» NP-полна.

We consider the MineSweeper game and its modification called Color MineSweeper. In this modification all closed cells are partitioned into certain classes and the function giving the number of mines in open cells is only partially known. We prove that the consistency problem of the game map of constant width L for Minesweeper and Color MineSweeper is tractable for L ϵ N and L = 1, respectively. For the case of Color MineSweeper and L > 1 the problem is shown to be NP-complete.