How to show that Color Tiles is NP-Complete

Question

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.

Answer 1

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.