91影视

$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,$鈭�$ is satisfied.

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