Ripple Effect is NP-complete

Ripple Effect is NP-complete. We reduce from 3-SAT.

The wire is of this form:

3’s carry the value True, 2’s carry the value False. We also keep track of the orientation, as reversing the orientation reverses the value carried by the wire. It can easily be shown that those two are the only local solutions. The gray squares will combine into a single region that will be filled by numbers appropriately.

We can “stretch” the wire arbitrarily long by inserting 4, 5, 6, and so on:

We can also bend wires:

And cross them:

Now that the basics are set, time to head to the more advanced gadgets:

To put an input:

To branch wires:

We only need one more gadget, the NAND gate.

Whose local solutions are:

(True/True)

(True/False; for False/True, flip)

(False/False)

With these gadgets, we can construct every possible Boolean formula or truth table, since we can create NOT, AND, OR, and TRUE:

And we can combine them in straightforward ways:

We can also combine them into an instance of 3-SAT, more or less following the above pattern (ORing the three literals in a clause and setting its result to TRUE).

This proves that Ripple Effect is NP-complete.

For fun, here’s a puzzle that simulates the equation :

Ripple Effect: x NAND -x = x

However, a faster result by betaveros, if we take Latin Square as NP-complete:

Puzzle 75: TomTom is NP-complete
Latin Square

Puzzle 75: TomTom Ripple Effect is NP-complete
Ripple Effect