<p>The reduction should not be too hard.</p>
<p>If you suppose that interaction can be done along fixed &quot;corridors&quot; (or &quot;lines&quot;) then you can easily build gadgets that mimic a SPLIT or CHOICE or OR gadget; for example:</p>
<p><a href="https://i.sstatic.net/Q7nHs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Q7nHs.png" alt="enter image description here" /></a></p>
<p>Assuming that interaction can be done only along the gray &quot;corridors&quot;, in the choice gadget, starting from A you can &quot;unlock&quot; only one of the two &quot;exits&quot; B or C. In the split gadget starting from A1,A2 you can unlock both exits.</p>
<p><a href="https://i.sstatic.net/x5qfL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/x5qfL.png" alt="enter image description here" /></a></p>
<p>In the OR gadget if at least one of the three block A, B, C can be unlocked then also the block D can be unlocked (D = A OR B OR C)</p>
<p>It's also easy to add a &quot;border&quot; structure of extra colored blocks that force interaction along the corridors; for example, it can be done using 4 distinct new colors used at the end of each corridor (&quot;North, South, East, West blocks&quot;) and filling the rest of the space with &quot;fixed&quot; 3x3 blocks with shifted colors.</p>
<p><a href="https://i.sstatic.net/kXG03.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kXG03.png" alt="enter image description here" /></a></p>
<p>Then you can make a reduction to Planar 3SAT creating a clause gadget in which if a variable of the clause is true you &quot;unlock&quot; enough &quot;points&quot; (and then you can collect N or more points if and only if all cluases are satisfied). Or you can reduce it to a simpler graph problem like Hamiltonian Path on Grid (induced) Graphs of max degree 3 (see <em>C. H. Papadimitriou and U. V. Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231–246</em> (Theorem 2)  )</p>
<p><strong>EDIT 2022-01-07</strong></p>
<p>The above gadgets can be used to easily prove that the problem of maximizing the score is NP-hard ; but with a trick it can also be converted to a problem in which all tiles can be removed if and only if the original Planar 3SAT is satisfiable.</p>
<p>The idea is to make a symmetric copy of the grid and separate it from the original one with a &quot;double wall&quot; of a new unused color &quot;Yellow&quot;. Then using the above gadgets make sure that a block of color Yellow can be unlocked and used to remove one of the central blocks of the wall if and only if all clauses are satisfied. For example:</p>
<p><a href="https://i.sstatic.net/TTh5D.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TTh5D.png" alt="enter image description here" /></a></p>
<p>When the two central blocks of the wall have been removed, hen all the wall can be cleared (up tiles vs bottom tiles). Without the tiles the left part of the grid matches the right part in reverse order, and all tiles can be cleared. For example:</p>
<p><a href="https://i.sstatic.net/Llv6L.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Llv6L.png" alt="enter image description here" /></a></p>
<p><strong>EDIT 2022-01-08</strong>*</p>
<p>I made a full example of a 3SAT formula; I only drawed the corridors (and I used extra colors to allow the corridors to cross each other and make other optimizations); you should complete the grid with N,S,W,E and fill blocks, then make the symmetric copy and central wall stuff. The <a href="https://www.nearly42.org/vdisk/games/colortiles/ColorTiles.pdf" rel="nofollow noreferrer">example can be downloaded here in PDF format</a>.</p>

CC BY-SA 4.0
2022-01-07T14:14:19.247Z
This looks like it works for proving NP-completeness of the problem of maximizing the number of points but I don't think this proves it for the problem of removing all the tiles (you can't clear the shifted color tiles). Unless there's some simple reduction from the N points version to the feasibility problem that I'm not seeing.
ColorTilesUser
CC BY-SA 4.0
2022-01-07T19:22:29.797Z
@ColorTilesUser you can use a trick to convert the "SCORE > N" version to the "CLEAR ALL TILES" version; see the updated answer.
Marzio De Biasi
CC BY-SA 4.0
2022-01-07T19:58:49.837Z
Th trick looks on the mark, or very close to it. What do you mean though by "A and B are from the distinct clause" and "When the clauses are satisfied" and why is the gadget different from the split and choice gadgets you had before. Based on the diagram, you can always clear each side of the gadget by clicking the horizontal greens with a B, then the vertical reds, then the horizontal greens with A, and  vertical reds again.  I'm not sure what that means for the values of the clauses.
ColorTilesUser
CC BY-SA 4.0
2022-01-07T20:48:47.163Z
@ColorTilesUser Block A should be "unlocked" if clause 1 is satisfied, block B if clause 2 is satisfied (the two clauses are not drawn). Both A and B are required to unlock the Yellow block (so it is an AND gadget). I would gladly draw a complete example of a 3SAT formula, but that would be pretty big; let me know if you need it for research purpouses.
Marzio De Biasi
CC BY-SA 4.0
2022-01-08T01:30:19.930Z
can you show me what the the gadget for an OR clause would look like?
ColorTilesUser
CC BY-SA 4.0
2022-01-08T19:45:34.767Z
@ColorTilesUser: I added the OR (clause) gadget in the answer (it's very simple)
Marzio De Biasi
CC BY-SA 4.0
2022-01-08T20:30:24.790Z
@ColorTilesUser: I also made a small full example that can be downloaded here: https://www.nearly42.org/vdisk/games/colortiles/ColorTiles.pdf
Marzio De Biasi
CC BY-SA 4.0
2022-01-07T00:00:42.760Z
2022-01-08T20:29:45.307Z
2022-01-08T20:29:45.307Z
Marzio De Biasi
<p>Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You can draw a horizontal or vertical line that intersects no other tile). If an empty grid cell has two or more tiles of the same color within it's view, then clicking on it will remove those tiles.
<a href="https://i.sstatic.net/uiWjc.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/uiWjc.png" alt="
![" /></a></p>
<p>The goal of the game is to remove all the tiles. You can play the game for yourself at <a href="https://en.gamesaien.com/game/color_tiles/" rel="nofollow noreferrer">https://en.gamesaien.com/game/color_tiles/</a></p>
<p>Based on intuition the problem seems to be NP-Complete but I can't find a way to reduce the problem into something resembling a known graph theoretic problem, say involving hypergraphs, mainly because removing tiles changes the graph structure. I've also thought about creating gadgets to try and reduce from 3-SAT, like how NP-completeness for Tetris was proved, which hasn't worked.</p>

CC BY-SA 4.0
2022-01-06T14:56:29.777Z
@D.W. done let me know if there's more I can add
ColorTilesUser
<graph-theory><np-hardness><np-complete>
How to show that Color Tiles is NP-Complete
ColorTilesUser
# How to show that Color Tiles is NP-Complete

(Asked by: username_0 on 2021-12-31)

Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You can draw a horizontal or vertical line that intersects no other tile). If an empty grid cell has two or more tiles of the same color within it's view, then clicking on it will remove those tiles.
[![
![](https://i.sstatic.net/uiWjc.png)](https://i.sstatic.net/uiWjc.png)

The goal of the game is to remove all the tiles. You can play the game for yourself at <https://en.gamesaien.com/game/color_tiles/>

Based on intuition the problem seems to be NP-Complete but I can't find a way to reduce the problem into something resembling a known graph theoretic problem, say involving hypergraphs, mainly because removing tiles changes the graph structure. I've also thought about creating gadgets to try and reduce from 3-SAT, like how NP-completeness for Tetris was proved, which hasn't worked.

**Tags:** graph-theory, np-hardness, np-complete

> **Comments:**
> **username_0**: @D.W. done let me know if there's more I can add  

---

## 1 answers

### Answer by username_1 on 2022-01-07. Score: 1 | Accepted answer

The reduction should not be too hard.

If you suppose that interaction can be done along fixed "corridors" (or "lines") then you can easily build gadgets that mimic a SPLIT or CHOICE or OR gadget; for example:

[![enter image description here](https://i.sstatic.net/Q7nHs.png)](https://i.sstatic.net/Q7nHs.png)

Assuming that interaction can be done only along the gray "corridors", in the choice gadget, starting from A you can "unlock" only one of the two "exits" B or C. In the split gadget starting from A1,A2 you can unlock both exits.

[![enter image description here](https://i.sstatic.net/x5qfL.png)](https://i.sstatic.net/x5qfL.png)

In the OR gadget if at least one of the three block A, B, C can be unlocked then also the block D can be unlocked (D = A OR B OR C)

It's also easy to add a "border" structure of extra colored blocks that force interaction along the corridors; for example, it can be done using 4 distinct new colors used at the end of each corridor ("North, South, East, West blocks") and filling the rest of the space with "fixed" 3x3 blocks with shifted colors.

[![enter image description here](https://i.sstatic.net/kXG03.png)](https://i.sstatic.net/kXG03.png)

Then you can make a reduction to Planar 3SAT creating a clause gadget in which if a variable of the clause is true you "unlock" enough "points" (and then you can collect N or more points if and only if all cluases are satisfied). Or you can reduce it to a simpler graph problem like Hamiltonian Path on Grid (induced) Graphs of max degree 3 (see *C. H. Papadimitriou and U. V. Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231–246* (Theorem 2) )

**EDIT 2022-01-07**

The above gadgets can be used to easily prove that the problem of maximizing the score is NP-hard ; but with a trick it can also be converted to a problem in which all tiles can be removed if and only if the original Planar 3SAT is satisfiable.

The idea is to make a symmetric copy of the grid and separate it from the original one with a "double wall" of a new unused color "Yellow". Then using the above gadgets make sure that a block of color Yellow can be unlocked and used to remove one of the central blocks of the wall if and only if all clauses are satisfied. For example:

[![enter image description here](https://i.sstatic.net/TTh5D.png)](https://i.sstatic.net/TTh5D.png)

When the two central blocks of the wall have been removed, hen all the wall can be cleared (up tiles vs bottom tiles). Without the tiles the left part of the grid matches the right part in reverse order, and all tiles can be cleared. For example:

[![enter image description here](https://i.sstatic.net/Llv6L.png)](https://i.sstatic.net/Llv6L.png)

**EDIT 2022-01-08**\*

I made a full example of a 3SAT formula; I only drawed the corridors (and I used extra colors to allow the corridors to cross each other and make other optimizations); you should complete the grid with N,S,W,E and fill blocks, then make the symmetric copy and central wall stuff. The [example can be downloaded here in PDF format](https://www.nearly42.org/vdisk/games/colortiles/ColorTiles.pdf).

> **Comments:**
> **username_0**: This looks like it works for proving NP-completeness of the problem of maximizing the number of points but I don't think this proves it for the problem of removing all the tiles (you can't clear the shifted color tiles). Unless there's some simple reduction from the N points version to the feasibility problem that I'm not seeing.  
> **username_1**: @username_0 you can use a trick to convert the "SCORE > N" version to the "CLEAR ALL TILES" version; see the updated answer.  
> **username_0**: Th trick looks on the mark, or very close to it. What do you mean though by "A and B are from the distinct clause" and "When the clauses are satisfied" and why is the gadget different from the split and choice gadgets you had before. Based on the diagram, you can always clear each side of the gadget by clicking the horizontal greens with a B, then the vertical reds, then the horizontal greens with A, and  vertical reds again.  I'm not sure what that means for the values of the clauses.  
> **username_1**: @username_0 Block A should be "unlocked" if clause 1 is satisfied, block B if clause 2 is satisfied (the two clauses are not drawn). Both A and B are required to unlock the Yellow block (so it is an AND gadget). I would gladly draw a complete example of a 3SAT formula, but that would be pretty big; let me know if you need it for research purpouses.  
> **username_0**: can you show me what the the gadget for an OR clause would look like?  
> **username_1**: @username_0: I added the OR (clause) gadget in the answer (it's very simple)  
> **username_1**: @username_0: I also made a small full example that can be downloaded here: https://www.nearly42.org/vdisk/games/colortiles/ColorTiles.pdf  

---

