Computers and Technology, 04.05.2021 18:50 devaughnnorthcu8221

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?

Answers: 3

Show answers

Another question on Computers and Technology

Computers and Technology, 24.06.2019 00:40

Use a software program or a graphing utility with matrix capabilities to solve the system of linear equations using an inverse matrix. x1 + 2x2 − x3 + 3x4 − x5 = 6 x1 − 3x2 + x3 + 2x4 − x5 = −6 2x1 + x2 + x3 − 3x4 + x5 = 3 x1 − x2 + 2x3 + x4 − x5 = −3 2x1 + x2 − x3 + 2x4 + x5 = 5

Answers: 3

Answer

Computers and Technology, 24.06.2019 11:20

Every telecommunication setup uses two devices: one device to transmit data and one device to receive data. which device transmits frequencies to mobile phones? towers transmit frequencies to mobile phones.

Answers: 1

Answer

Computers and Technology, 24.06.2019 21:40

Which of these is not a type of socket? aga (alternating grid array) pga (pin grid array) spga (staggered pin grid array) lga (land grid array)

Answers: 1

Answer

Computers and Technology, 24.06.2019 22:50

Which of these might be an example of an advertiser's target group? a.people who have no access to media b.people the advertisers know nothing about c. people who watch a variety of tv shows d. people who live in the same region of the country

Answers: 2

Answer

You know the right answer?

Minesweeper is a game played on a rectangular n by m grid. A number k is given representing the numb...

Questions