In the following solitaire game, you are given an$\mathit{m}\mathbf{\times }\mathit{m}$ board. On each of its$\mathit{m}\mathbf{2}$ positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board until each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. Let$\mathbf{S}\mathbf{O}\mathbf{L}\mathbf{I}\mathbf{T}\mathbf{A}\mathbf{I}\mathbf{R}\mathbf{E}\mathbf{}\mathbf{=}\mathbf{\{}\mathbf{}\mathbf{<}\mathbf{G}\mathbf{>}\mathbf{}\mathbf{|}\mathbf{G}$ is a winnable game configuration}. Prove that $\mathit{S}\mathit{O}\mathit{L}\mathit{I}\mathit{T}\mathit{A}\mathit{I}\mathit{R}\mathit{E}$is $\mathit{N}\mathit{P}\mathbf{-}\mathit{c}\mathit{o}\mathit{m}\mathit{p}\mathit{l}\mathit{e}\mathit{t}\mathit{e}$.

$SOLITAIRE$is in$NP$:

$SOLITAIRE\$\backslash inNP\$$because it can be verified that a solution works in polynomial time.

Every Language in$NP$is polynomial time reducible to$SOLITAIRE$ :

We know that " role="math" localid="1663227043731" $3SAT\$=\backslash \{\backslash langle\backslash phi\backslash rangle\backslash mid\backslash phi\$$is a satisfiable $\$3\backslash mathrm\left\{cnf\right\}-\$$formula $\$\backslash \}$" $\$$, three variables.

And "$3SAT$is$NP-Complete$.

So, if we show that role="math" localid="1663227063355" $\$3\backslash mathrm\left\{SAT\right\}\backslash leq\{\backslash mathrm\{p\left\}\right\}\$ SOLITAIRE$then $SOLITAIRE$is also $NP-Complete$.

Given $\phi$ with m variables $\$V\_\left\{1\right\}$, $\backslash ldots$, $\$V\_\left\{m\right\}\$$and k clauses $\$C\_\left\{1\right\}$, $\backslash ldots$, $C\_\left\{k\right\}\$$

Now construct the following game$g$ with $\$k \backslash times m\$$board.

Construction of $\$k \backslash times m\$$game of $G$.

Let us assume that $\phi$ has no clauses that contain both $\$V\_\left\{i\right\}\$$and $\$\backslash bar\$V\_\left\{i\right\}\$$because such clauses may

If the variable $\$V\_\left\{i\right\}\$$is in clause $\$C\_\left\{i\right\}\$$then put a blue stone in row$\$C\_\left\{i\right\}\$$ column$\$V\_\left\{i\right\}\$$.

If the variable$\$\backslash bar\$V\_\left\{i\right\}\$$ is in clause$\$C\_\left\{i\right\}\$$ then put a red stone in row$\$C\_\left\{i\right\}\$$ , column$\$V\_\{i\backslash text\{then\left\}\right\} \$$

$K*m$board can be changed to square board necessary without affecting solvability.

Now we need to show that $\$\backslash phi\$$is satisfiable if and only if$G$ has a solution:

If is satisfiable then has a solution(Forward direction):

A Satisfying assignment is taken.

If V is true, remove the rod stone from the corresponding column.

If V is false, remove the blue stone from corresponding column.

So, stones corresponding to true literals remains.

Because every clause has a true literal, every row has a stone.

Therefore,$G$ has a solute or.

Take a game solution.

If the red stone removed from a column, set the corresponding variable true.

If the bluestone is removed from a column, set the corresponding variable false.

Every row has a stone remaining, so every clause has a true literal.

Therefore,$\varnothing$ is satisfied.

Thus,$SOLITAIRE$ is $NP-Complete$.