In the following solitaire game, you are given an m * n board.On each of its n2
ID: 3608789 • Letter: I
Question
In the following solitaire game, you are given an m * n board.On each of its n2 positions lies either 'a blue stone', 'a redstone', or nothing at all. You play by removing stones from theboard so that each column contains only stones of a single colorand each row contains at least one stone. You win if you achievethis objective. Winning may or may not possible, depending upon theinitial configuration. Let SOLITAIRE = {(G) | G is a winnable gameconfiguration}. Prove that SOLITAIRE is NP-complete. In the following solitaire game, you are given an m * n board.On each of its n2 positions lies either 'a blue stone', 'a redstone', or nothing at all. You play by removing stones from theboard so that each column contains only stones of a single colorand each row contains at least one stone. You win if you achievethis objective. Winning may or may not possible, depending upon theinitial configuration. Let SOLITAIRE = {(G) | G is a winnable gameconfiguration}. Prove that SOLITAIRE is NP-complete.Explanation / Answer
If xi is in cj put a blue stone in rowcj, column xi. If xi’ is in clausecj put a red stone in row cj, column xi.The board can be made square by repeating a row or adding a blankcolumn as necessary without affecting solvability. Now show that is satisfiable iff G has a solution.
We have to show both directions.
Take a satisfying assignment:
If xi is true (false), remove the red (blue) stonesfrom the corresponding column. Stones corresponding to trueliterals remains. Since every clause has a true literal, every rowhas a stone.
Take a game solution:
If the red (blue) stones were removed from a column, set thecorresponding variable true (false). Every row has a stoneremaining, so every clause has a true literal. Therefore issatisfied.
I hope this will helpfulfor you..............
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.