You are given a puzzle consists of an m x n grid of squares, where each square can be empty, occupied by a red stone, or occupied by a blue stone. The goal of the puzzle is to remove some of the given stones so that the remaining stones satisfy two conditions: (1) every row contains at least one stone, and (2) no column contains stones of both c colors. It is easy to see that for some initial configurations of stones, reaching this goal is impossible. We define the Puzzle problem as follows. Given an initial configuration of red and blue stones on an m x n grid of squares, determine whether or not the puzzle instance has a feasible solution. Prove that the Puzzle problem is NP-complete.

You are given a puzzle consists of an m x n grid of squares, where each square can be empty, occupied by a red stone, or occupied by a blue stone. The goal of the puzzle is to remove some of the given stones so that the remaining stones satisfy two conditions: (1) every row contains at least one stone, and (2) no column contains stones of both c colors. It is easy to see that for some initial configurations of stones, reaching this goal is impossible. We define the Puzzle problem as follows. Given an initial configuration of red and blue stones on an m x n grid of squares, determine whether or not the puzzle instance has a feasible solution. Prove that the Puzzle problem is NP-complete.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

You are given a 2 by n grid, where the cell on row i column j contains a non-negative number ai,j . You can start at either cell in the lefttmost column, and your goal is to reach either cell in the rightmost column by a sequence of moves. You can move to an adjacent cell (if it exists) in each of the 4 cardinal directions (up,down, left and right). A path achieves a score equal to the sum of values in its cells. Note that a cell which is used twice in a path only counts its value once to the score of that path.Design an algorithm which runs in O(n) time and finds a path of minimum score from the leftmost column to the rightmost column.
Dingyu is playing a game defined on an n X n board. Each cell (i, j) of the board (1 2, he may only go to (2, n).) The reward he earns for a move from cell C to cell D is |value of cell C – value of cell D|. The game ends when he reaches (n, n). The total reward - is the sum of the rewards for each move he makes. For example, if n = 1 2 and A = 3 the answer is 4 since he can visit (1, 1) → (1, 2) → (2, 2), and no other solution will get a higher reward. A. Write a recurrence relation to express the maximum possible reward Dingyu can achieve in traveling from cell (1, 1) to cell (n, n). Be sure to include any necessary base cases. B. State the asymptotic (big-O) running time, as a function of n, of a bottom-up dynamic programming algorithm based on your answer from the previous part. Briefly justify your answer. (You do not need to write down the algorithm itself.)
Imagine there are N teams competing in a tournament, and that each team plays each of the other teams once. If a tournament were to take place, it should be demonstrated (using an example) that every team would lose to at least one other team in the tournament.
You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack. A queen is standing on an chessboard. The chess board's rows are numbered from to , going from bottom to top. Its columns are numbered from to , going from left to right. Each square is referenced by a tuple, , describing the row, , and column, , where the square is located. The queen is standing at position . In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from : There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location in the diagram above prevents the queen from attacking cells , , and : Given the queen's position and the locations of all the obstacles, find and print the number of…
You are a computer research scientist at Tesla, and your task is to create a computer vision application for self-driving cars to detect object and avoid collision. You know that Graham's scan is a method of computing the convex hull of a finite set of points in the plane. You decide to apply this algorithm to achieve the goal of your task. a) Suppose Graham's scan executes n points, where n >= 3. Prove that, at the end of the program, the stack S consists of, from bottom to top, exactly the vertices of convex hull in counter-clockwise order.
On a chess board of r rows and c columns there is a lone white rook surrounded by a group of opponent's black knights. Each knight attacks 8 squares as in a typical chess game, which are shown in the figure - the knight on the red square attacks the 8 squares with a red dot. The rook can move horizontally and vertically by any number of squares. The rook can safely pass through an empty square that is attacked by a knight, but it must move to a square that is not attacked by any knight. The rook cannot jump over a knight while moving. If the rook moves to a square that contains a knight, it may capture it and remove it from the board. The black knights. never move. Can the rook eventually safely move to the designated target square? The figure illustrates how the white rook can move to the blue target square at the top-right corner in the first sample case. The rook captures one black knight at the bottom-right of the board on its way. Rok nd kight lcoes by Chunen Input The first line…
Computer Science There is an n × n grid of squares. Each square is either special, or has a positive integer costassigned to it. No square on the border of the grid is special.A set of squares S is said to be good if it does not contain any special squares and, starting fromany special square, you cannot reach a square on the border of the grid by performing up, down,left and right moves without entering a cell belonging to S. 5 3 4 9 4 X 3 6 1 9 X 4 1 2 3 5 - Design an algorithm which receives an arbitrary n × n grid, runs in time poly-nomial in n and determines a good set of squares with minimum total cost.
In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…
The puzzle called the Towers of Hanoi consists of three pegs, one of which contains several rings stacked in order of descending diameter from bottom to top. The problem is to move the stack of rings to another peg. You are allowed to move only one ring at a time, and at no time is a ring to be placed on top of a smaller one. Observe that if the puzzle involved only one ring, it would be extremely easy. Moreover, when faced with the problem of moving several rings, if you could move all but the largest ring to another peg, the largest ring could then be placed on the third peg, and then the problem would be to move the remaining rings on top of it. Using this observation, develop a recursive algorithm for solving the Towers of Hanoi puzzle for an arbitrary number of rings.
Mastermind is a code-breaking game for two players. In the original real-world game, one player A selects 4 pegs out of 6 colors and puts them in a certain fixed order; multiples of colors are possible (for example, red-green red-green). His opponent B does not know the colors or order but has to find out the secret code. To do so, B makes a series of guesses, each evaluated by the first player. A guess consists of an ordered set of colors which B believes is the code. The first player A evaluates the guess and feeds back to B how many positions and colors are correct. A position is correct ("black") if the guess and the secret code have the same color. Additional colors are correct ("white"), if they are in the guess and the code, but not at the same location. For example1 2 3 4secret: red-green red greenguess: red blue green purpleresults in one correct position ("black = 1") for the red peg at position one and one additional correct color ("white=1") for the green peg in the guess.…
An n × n square consists of black and white cells arranged in a certain way. The problem is to determine the number of white areas and the number of white cells in each area. For example, a regular 8 × 8 chessboard has 32 one-cell white areas; the square in Figure 5.22a consists of 10 areas, 2 of them of 10 cells, and 8 of 2 cells; the square in Figure 5.22b has 5 white areas of 1, 3, 21, 10, and 2 cells. Write a program that, for a given n × n square, outputs the number of white areas and their sizes. Use an (n + 2) × (n + 2) array with properly marked cells. Two ad- ditional rows and columns constitute a frame of black cells surrounding the entered square to simplify your implementation. For instance, the square in Figure 5.22b is stored as the square in Figure 5.22c. (a–b) Two n 3 n squares of black and white cells and (c) an (n + 2) 3 (n + 2) array implementing square (b). bbbbbbbbbb bwbbwwbwwb bbbbbwbwwb bwwwbbwwwb bwbwbwwbbb bwbwwwbwbb bwbbbbwwwb bwbwbbwwwb bwbwbbwwwb…
Consider a maze represented by a matrix of m rows and n columns with obstacles (see the figure below). A cell with a value = -1 is an obstacle that cannot be overcome. The goal is to start from cell [0, 0] and reach the last cell [m-1, n-1]. This may be possible by taking several paths. Count the number of these paths. The movement is allowed from cells (i+ 1, j) and (i, j+ 1) only. -1 -1 Provide two solutions, one iterative and one recursive to the above problem.