The game PEBBLES is played on a k n chessboard. Initially eachsquare of the chessboard has
Question:
The game PEBBLES is played on a k × n chessboard. Initially eachsquare of the chessboard has a black pebble, or a white pebble, orno pebble. You play the game by removing pebbles one at a time. Youwin the game if you can end up with a board in which each columncontains only pebbles of a single color and each row contains atleast one pebble. (a) Show that the set of winnable PEBBLES gamesis in NP. Hint: Describe a nondeterministic polynomial-timealgorithm to determine whether a given PEBBLES board is winnable.(b) Given a boolean expression E in 3-CNF with k clauses and nvariables, construct the following k × n board: If literal xi is inclause cj , put a black pebble in column xi , row cj . If literalxi is in clause cj , put a white pebble in column xi , row cj .Show that E is satisfiable if and only if this PEBBLES game iswinnable.
Expert Answer:
a To show that the set of winnable PEBBLES games is in NP we can describe a nondeterministic polynom... View the full answer
