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:00

Which tool could be used to display only rows containing presidents who served two terms

Answers: 3

Answer

Computers and Technology, 24.06.2019 01:00

Me if you do then you get 10 points and brainliest

Answers: 1

Answer

Computers and Technology, 24.06.2019 13:20

3. ranga ramasesh is the operations manager for a firm that is trying to decide which one of four countries it should research for possible outsourcing providers. the first step is to select a country based on cultural risk factors, which are critical to eventual business success with the provider. ranga has reviewed outsourcing provider directories and found that the four countries in the table that follows have an ample number of providers from which they can choose. to aid in the country selection step, he has enlisted the aid of a cultural expert, john wang, who has provided ratings of the various criteria in the table. the resulting ratings are on a 1 to 10 scale, where 1 is a low risk and 10 is a high risk. john has also determined six criteria weightins: trust, with a weight of 0.3; quality, with 0.2; religious, with 0.1; individualism, with 0.2; time, with 0.1; and uncertainity, with 0.1. using the factor-rating method, which country should ranga select? why? (2 points)

Answers: 3

Answer

Computers and Technology, 25.06.2019 01:00

When a new name is registered on the internet, the process can take two hours to four hours four hours to three days two hours to two days one hour to eight hours

Answers: 1

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