# Can I Clear The Grid?

I recently found this game and have been enjoying it. Basically, there is a grid of colored tiles and you act by clicking on empty spaces. When you click an empty space, the first tile (if any) in each of the four axis-aligned directions is selected. If any color appears more than once, all tiles of that color are destroyed (and if it hits two of one color and two of another, all four are destroyed).

See the following example:

. . R . .      . . . . .      . . . . .
R---x G .      . . . G .      . . . . .
. . | . .  =>  . . . | .  =>  . . . . .
. G | . R      . G---x R      . . . . R
. . R . .      . . . . .      . . . . .


The game is played on a time limit and clicking a space that does nothing will incur a time penalty, but for this challenge, I am just interested in one thing: can I clear the entire grid?

For example, in this grid, two clicks are enough to clear the grid:

. R . .
. B . B
. R . .


Clicking between the Bs opens a space between the Rs that can be clicked to finish it.

On the other hand, in this grid, there is no way to eliminate all tiles:

G . G . G


If you click between the right two Gs, then you can't eliminate the left one, and same for the other direction.

Given a grid represented as any reasonable format (for example, a matrix of non-negative integers where spaces are 0 is what I predict will be most common), output whether or not the grid can be cleared (refer to the consensus for output format).

You may assume there will be no more than 9 colors; this is so that input can be taken as a list of strings of digits.

Here are some example test cases. The following are all clearable:

. R . G
B . B .
. R . G

[[0, 1, 0, 2], [3, 0, 3, 0], [0, 1, 0, 2]]

. R G .
R . . G
. R G .

[[0, 1, 2, 0], [1, 0, 0, 2], [0, 1, 2, 0]]

. R . G
R . G R
. R . .

[[0, 1, 0, 2], [1, 0, 2, 1], [0, 1, 0, 0]]

R G . G
G R . .
. . R G
G . G R

[[1, 2, 0, 2], [2, 1, 0, 0], [0, 0, 1, 2], [2, 0, 2, 1]]


The following are not:

. R G .
G . . R
G . . R
. R G .

[[0, 1, 2, 0], [2, 0, 0, 1], [2, 0, 0, 1], [0, 1, 2, 0]]

R . R . R

[[1, 0, 1, 0, 1]]

R . .
. . R
. R .

[[1, 0, 0], [0, 0, 1], [0, 1, 0]]

R G R G
[[1, 2, 1, 2]]

. R B .
R . G R
. G B .
[[0, 1, 3, 0], [1, 0, 2, 1], [0, 2, 3, 0]]


You may assume that the board contains at least one cell, but either [[0]] or [[1]] are valid test cases.

This is a challenge, so the shortest submission (in bytes) for each language is the winner!

• Nice challenge idea. Commented Mar 19 at 19:52
• Suggested test case: [[0, 1, 3, 0], [1, 0, 2, 1], [0, 2, 3, 0]] -> False Commented Mar 20 at 15:48
• Test cases with more than two colors would be helpful. Commented Mar 20 at 16:44
• @JonathanAllan Hmm, I'll allow you to assume that the board is non-empty but not that there is a space cell. Commented Mar 23 at 1:26

# JavaScript (ES11), 185 bytes

-3 thanks to l4m2

Expects a matrix of digits (with 0 for empty) and returns a Boolean value.

f=m=>m.some(z=(r,y)=>r.some((k,x)=>k?z=0:(h=M=>[-1,0,1,2].map(g=d=>(v=m[Y=y+d%2*++k]?.[X=x+~-d%2*k])<1?g(d):k=M?h[v]?M[Y][X]=0:0:![h[v]|=h[v]+v]))()|h(M=m.map(r=>[...r]))|M<m&&f(M)))!=z


Attempt This Online!

### Method

For each empty cell in the input matrix, we call a helper function h twice:

• once with no argument to count the colors of the closest non-empty cells in the 4 directions
• once with a new copy M of the matrix to remove from M the cells whose color appears at least twice; if some deletions occur, it triggers a recursive call to the main function with the updated matrix

### Commented

f = m =>                          // f is a recursive function taking a matrix m[]
m.some(z = (r, y) =>              // for each row r[] at index y in m[]:
r.some((k, x) =>                //   for each value k at index x in r[]:
k ?                           //     if k is not zero:
z = 0                       //       at least 1 non-empty cell -> clear z
:                             //     else:
( h = M =>                  //       h is a helper function taking M
[-1, 0, 1, 2]             //       we have 4 directions to test
.map(g = d =>             //       for each direction d:
( v = m[                //         load in v the value of the cell at:
Y = y + d % 2 * ++k //           Y = y + dy * k (where k is pre-
]?.[                  //           incremented)
X = x + ~-d % 2 *k  //           X = x + dx * k
]                     //
) < 1 ?                 //         if this cell is defined and empty:
g(d)                  //           move further in the same direction
:                       //         else:
k =                   //           reset k to 0 in all cases
M ?                   //           if M is defined:
h[v] ?              //             if h[v] is greater than 0:
M[Y][X] = 0       //               clear M[Y][X]
:                   //             else:
0                 //               do nothing
:                     //           else:
![ h[v] |=          //             set h[v] = 0 if h[v] is undefined
h[v] + v       //             or h[v] > 0 if h[v] = 0 and v is
]                   //             defined
)                         //       end of map()
)() |                       //     1st call to h with M undefined
h(M = m.map(r => [...r])) | //     2nd call to h with M = copy of m[]
M < m && f(M)               //     do a recursive call if M was modified
)                               //   end of some()
) != z                            // end of some() / success if z was not cleared

• – l4m2
Commented Mar 20 at 1:34
• h[v]+v/v|0 => h[v]+v|0 as we don't care what number is added
– l4m2
Commented Mar 21 at 9:15
• @l4m2 Nice catch. We can save another byte with h[v]|=h[v]+v. Commented Mar 21 at 9:44

# Charcoal, 109 bytes

ＷＳ⊞υ⁻ι ≔⟦υ⟧υＦυＦＬιＦ⌕Ａ§ικ.«ιＪλκ≔Ｅ⁴ＫＤＬ⁺ι⌊ι✳⊗μθ≔ＥθΦ⁻⪫μω.¬πηＦΦ⁴∧§ημ⊖№η§ημ§≔§θμ⌕§θμ§ημ.≔⪪⪫ＫＡωＬ⌊ιεＦ¬⁼ει⊞υε⎚»⊙υ⬤ι¬⁻λ.


Try it online! Link is to verbose version of code. Takes input as in the diagrams in the question but any character other than . and space may be used as a colour. Explanation:

ＷＳ⊞υ⁻ι ≔⟦υ⟧υＦυ


Input the board and start a breadth-first search with that position.

ＦＬιＦ⌕Ａ§ικ.«


Loop over all of the indices of .s in the current position.

ιＪλκ


Temporarily draw the position to the canvas and jump to the current ..

≔Ｅ⁴ＫＤＬ⁺ι⌊ι✳⊗μθ


Peek in all four orthogonal directions.

≔ＥθΦ⁻⪫μω.¬πη


Get the first non-. character (if any) in each direction.

ＦΦ⁴∧§ημ⊖№η§ημ


Loop over those characters that appear more than once.

§≔§θμ⌕§θμ§ημ.


Replace the character with a .

≔⪪⪫ＫＡωＬ⌊ιε


Read the position back from the canvas.

Ｆ¬⁼ει⊞υε


If this was a new position (i.e. at least two letters were replaced) then add it to the list of positions to search.

⎚


Clear the canvas ready for the next iteration.

»⊙υ⬤ι¬⁻λ.


See if any position has no letters left.

• I'm pretty sure you can just take the input without spaces, so you can replace the Minus(i, " ")/⁻ι  with i/ι to save 2 bytes. Commented Mar 20 at 12:34
• @KevinCruijssen Sure but this way made it easier to paste in the test cases.
– Neil
Commented Mar 20 at 13:21
• (Also, in case you missed it, codegolf.stackexchange.com/a/271912)
– Neil
Commented Mar 20 at 13:24
• I did miss it indeed, but I'm afraid I'd first have to investigate how to calculate the atan2 manually in the first place.. Based on the \u, I see there are six escape characters and four regular characters among the remaining digits/letters. Seem rather short. 🤔 Commented Mar 20 at 14:09
• @KevinCruijssen That's because it had an error. I've updated it so you've got five more days in which to crack it.
– Neil
Commented Apr 5 at 16:37

# Python3, 368 bytes

E=enumerate
def f(b):
q=[{(x,y):v for x,r in E(b)for y,v in E(r)}]
for d in q:
if sum(d.values())==0:return 1
for i in d:
if 0==d[i]:
D={}
for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
j,k=i
while(c:=(j+X,k+Y))in d:
if d[c]:D[d[c]]=D.get(d[c],[])+[c];break
j,k=c
if(U:={**d,**{I:0 for J in D for I in D[J]if len(D[J])>1}})!=d:q+=[U]


Try it online!

# Python 3, 260 bytes

def f(a,w,h):
if~-any(a):return 1
for x in range(w*h):
n=a[:];c=[];[c:=c+[(v,x+i*s)for i,v in enumerate(a[x::s][:t])if v][:1]for s,t in((-w,h),(w,h),(-1,x%w+1),(1,w-x%w))]
for v,i in c:n[i]*=v not in[u for u,j in c if i-j]
if n!=a and f(n,w,h):return 1


Try it online!

Takes input as a 1d array of integers a where 0 is an empty cell, and grid dimensions w,h. Outputs 1 for true and None for false.

The function works by trying every move and for each move that removes any tiles it makes a recursive call.

# Jelly, 45 bytes

œị¹ƙ⁸ḊƇŒṬ€S¬a
ŒṪ_ẠÐḟṠAÞḢ$ƙ$+ç⁸
¬sŒṪȦ?ç@€⁻Ƈ⁸ß€


A full program that accepts a list of non-empty* lists of non-negative integers where 0 is a space, outputting via its exit code - 1 when possible, 0 otherwise.

Try it online! Or see the test-suite (uses a zsh wrapper to catch the exit code).

* Would identify [[]] as impossible if given, can be handled for +1 byte by inserting 0 between ¬sŒṪȦ? and ç@€⁻Ƈ⁸ß€.

#### How?

œị¹ƙ⁸ḊƇŒṬ€S¬a - Link 1 (Remove equal colours): ColourCoordinates, Board
œị¹ƙ⁸         - Group the ColourCoordinates by their colours on the Board
ḊƇ       - keep those groups with length greater than one
ŒṬ€    - covert each into a 2d array with ones at the given coordinates
S   - sum them to a single mask
¬  - logical NOT (vectorises)
a - logical AND {Board} (vectorises)
-> a copy of Board with identified equal colours set to zero

ŒṪ_ẠÐḟṠAÞḢ$ƙ$+ç⁸ - Link 2 (Try pressing): Board, SpaceCoordinate
ŒṪ               - truthy coordinates {Board} -> all ColourCoordinates
_              - {those} subtract {SpaceCoordinate} (vectorises) -> Offsets
ẠÐḟ           - {Offsets} discard if all
-> those Offsets for colours in SpaceCoordinate's row or column
$- last two links as a monad - f(Offsets): Ṡ - sign (vectorises) (e.g. [0, -3] -> [0, -1] or [4, 0] -> [1, 0]) ƙ - apply to groups of {Offsets} with equal {Sign}s:$      -     last two links as a monad - f(Offsets):
AÞ        -        sort by absolute value
Ḣ       -        head -> closest Offset in the direction of {Sign}
+   - add {SpaceCoordinate} -> back from Offsets to coordinates
ç⁸ - call Link 1 - f(that, Board)

¬sŒṪȦ?ç@€⁻Ƈ⁸ß€ - Main Link: list of lists of non-negative integers, Board
¬              - logical NOT {Board} (vectorises) -> 1s at spaces, 0s at colours
?         - if...
Ȧ          - ...condition: any and all? -> 1 if all spaces else 0
s             - ...then: split {that} into chunks of length {Board} (vectorises)
-> error! (can't split into chunks of length zero)
ŒṪ           - ...else: truthy coordinates -> SpaceIndices
ç@€      - call Link 2 with swapped arguments for each
⁻Ƈ⁸   - keep only those which have changed
ß€ - call this (Main) Link for each