Minesweeper is a game played on a rectangular n by m grid. A number k is given representing the number of mines that are hidden in the grid, with each grid location having either zero or one mine; however, the locations of the mines are unknown. Some locations of the grid are labeled with numbers between 0 and 8, representing the number of adjacent locations with mines (diagonally adjacent is counted as adjacent, and there can be no mine on the labeled grid location). A Minesweeper position is thus a specification of n, m,k and the numeric labels for labeled grid locations. Given such a position, solution to the game is a selection of k grid locations proposed for the mines such that each numeric label "i" is adjacent to exactly "i" selected mine locations. When playing this game, a player wants to identify safe grid locations, that is, grid locations where no solution places a mine.

Required:
a. Define a decision problem in NP that is being solved by a player trying to identify whether a particular grid location is safe or not safe. (Hint: it will matter whether "yes" or "no" means safe.)
b. Argue that your decision problem is in the class NP.
c. Suppose you wanted to show your problem NP-hard. What reduction could you find to show this?