How to show that Color Tiles is NP-Complete

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.

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.

• @D.W. done let me know if there's more I can add Jan 6, 2022 at 14:56

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:

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.

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.

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:

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:

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.

• 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. Jan 7, 2022 at 14:14
• @ColorTilesUser you can use a trick to convert the "SCORE > N" version to the "CLEAR ALL TILES" version; see the updated answer. Jan 7, 2022 at 19:22
• 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. Jan 7, 2022 at 19:58
• @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. Jan 7, 2022 at 20:48
• can you show me what the the gadget for an OR clause would look like? Jan 8, 2022 at 1:30