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 contain at least one pebble.

(a) Show that the set of winnable PEBBLES games is in NP by describing a nonde-terministic 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 kn 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.

(c) What can you conclude from (a) and (b)?