The game PEBBLES is played on a k × n chessboard. Initially each square of the c

Question

The game PEBBLES is played on a k × n chessboard. Initially each square of the chessboard has a black pebble, or a white pebble, or no pebble. You play the game by removing pebbles one at a time. You win the game if you can end up with a board in which each column contains only pebbles of a single color and each row contains at least one pebble. (a) Show that the set of winnable PEBBLES games is in NP. Hint: Describe a nondeterministic polynomial-time algorithm to determine whether a given PEBBLES board is winnable. (b) Given a boolean expression E in 3-CNF with k clauses and n variables, construct the following k × n board: If literal xi is in clause cj , put a black pebble in column xi , row cj . If literal xi 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 is winnable.

Explanation / Answer

Solution:

a) If part: Let E be a boolean expression in 3-CNF with k clauses c1, c2,....,ck and n variables x1, x2, .....,xn and assume no clause contains both xi and !xi. suppose the PEBBLES game constructed from E has been won. If all the white pebbles have been removed from column xi leaving only black pebles, set the corresponding variable xi in E to true. If all the black pebbles have been removed from a column x1 leaving only white pebbles, set the corresponding variable xi in E to false. since every row cj has at least one pebble left in the won game, each clause cj in E has at least one true literal. This means E is satisfiable.

b) If part: Let E be a boolean expression in 3-CNF with k clauses c1, c2,....,ck and n variables x1, x2, .....,xn and assume no clause contains both xi and !xi. suppose the PEBBLES game constructed from E has been won. If all the white pebbles have been removed from column xi leaving only black pebles, set the corresponding variable xi in E to true. If all the black pebbles have been removed from a column x1 leaving only white pebbles, set the corresponding variable xi in E to false. since every row cj has at least one pebble left in the won game, each clause cj in E has at least one true literal. This means E is satisfiable.

Only- if part: Suppose T is a truth assignment that sacrifies E. If xi is set to true, remove all the white pebbles from the corresponding column. Pebbles corresponding to true literals are left and becausse every clause has at least one true literal, every row has at least one pebble.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.