Is this Flow Free puzzle trivial?

Question

Background

Flow Free is a series of puzzle games whose objective is to connect all the same-colored pairs of dots on the grid. In this challenge, we consider the original game on a rectangular grid (no variations like bridges, warps, or hexagonal grids).

A puzzle in Flow Free might look like this:

Puzzle Solution
....1 11111
..... 13333
..24. 13243
1.... 13243
23... 23243
...43 22243

One of the easiest techniques in the puzzle is that, if you can connect two dots by following the "border cells" in only one way, such a connection is always correct.

Border cells are unsolved cells that are (orthogonally or diagonally) adjacent to a solved cell (including those outside of the grid).

In order to use this technique, the two dots themselves must also be border cells, and two adjacent border cells can be connected only if they're adjacent to some common solved cell. See the explanation below for an illustration.

A puzzle is said to be "trivial" if this technique can be used from the start to the end.

The above example is an example of a trivial puzzle. Let's see how it is so.

Puzzle Border Trivial pair
....1 ##### 11111
..... #...# 1...#
..24. #...# 1...#
1.... #...# 1...#
23... #...# #...#
...43 ##### #####
 .... #### 3333
 .24. #..# 3..3
 .... #..# 3..3
23... ##..# #3..3
...43 ##### ####3
 24 ## 24
 .. ## 24
2 .. # ## 2 24
...4 #### 2224

Note that, in the last step, the following paths are not considered because a horizontal connection in the middle of the width-2 strip is not valid ("two adjacent border cells can be connected only if they're adjacent to some common solved cell"):

 2. .4
 22 44
2 22 . 4.
222. ..44

Challenge

Given a solved Flow Free puzzle, determine if it is trivial.

The input can be taken as a single string/array or a list of lines. You may assume only the digits 1-9 are used, and each line represented by each digit is a valid polystrip of length 3 or higher.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Truthy (is trivial)

11111
12221
11113
33333
32222
11111
13333
13243
13243
23243
22243

Falsy (is not trivial)

m90 provided the last test case, which is specifically constructed to use an invalid bridge (the line 5).

11121
13121
13121
13111
11122
13121
13121
33111
13333
13443
13343
11243
21243
22244
1116777
1226666
1125555
5555344
8888334
9998444

• tsh: Is ????? 13?31 ?242? ?????? ?4??? ????? trivial? How can I trivially know 1 is connected use upper half border other than the another part?
• Bubbler: @tsh That one is not trivial in this challenge's definition ("if you can connect two dots by following the "border cells" in only one way..."), though a different kind of logic can easily say that 1 goes through the top border.
• tsh: Does this mean that ??2???2 ????1?1 is trivial but 2?????2 ????1?1 is not. And 2222222 2222111 is ambiguous?
• Jonathan Allan: 1. "Border cells are unsolved cells" - the example shows given, solved cells as border cells. 2. "Border cells are unsolved cells that are (orthogonally or diagonally) adjacent to a solved cell (including those outside of the grid)." - the example does not show border cells that are adjacent to solved cells but not adjacent to the outside of the grid. 3. "two adjacent border cells can be connected only if they're adjacent to some common solved cell" - how does that hold for the 1s in the example?
• Bubbler: @JonathanAllan 1. Given cells count as unsolved until they become connected. 2. Maybe you're confused because I'm removing the solved lines in the previous step from the picture. e.g. a line of 1s is implicit in the 2nd pic, so some of the #s there are actually bordering the solved 1 cells. 3. Think of the outside of the grid as filled with implicit solved cells - "Border cells are unsolved cells that are (orthogonally or diagonally) adjacent to a solved cell (including those outside of the grid)". 4. It just means that 2 and 4 can be completed one by one in any order.

Answer 1

Python 3, 331 bytes

def T(p):
 w=len(p[0])+2;p='..'.join(p).join(['.'*(w+1)]*2);d={};N={}
 for i,c in enumerate(p):d[c]=d.get(c,set())|{i};N[i]={i-w-1,i-w,i-w+1,i-1,i+1,i+w-1,i+w,i+w+1}
 u=d.pop('.')
 while d:
 for k,v in d.items():
 if not any(abs(a-b)in(1,w)and not(N[a]&N[b]&u)for a in v for b in v):u|=v;d.pop(k);break
 else:return 0
 return 1

Try it online!

Takes a list of strings. Returns 1 for a trivial solution, otherwise returns 0. On TIO it is run against all the test cases.

Here's brief explanation:

p is converted to a long string with '.' marking the initial out-of-bounds cells. This is so neighbors don't need to be checked if their outside the grid.

d is a dict mapping symbols in the solution to their set of indexes in p.

N maps indexes to neighbors.

u is a set of used (i.e., solved) cells. It gets initialized to the indices of the '.'s in p.

k and v are a symbol from the grid and it's set indices in p.

if not any(...) makes sure that any adjacent indices in v have a common neighbor cell in u. If True, v is a valid trivial path, it is added to u and removed from d; and the for k,v loop is exited early.

If the for k,v... loop runs to the end, there aren't any trivial paths, so return 0 (Falsey).

If while d ends, all the paths were trivial, so return 1 (Truthy).

Answer 2

BQN, (削除) 124 (削除ここまで) 114 bytes

∨ ́{0=F⥊x?1;W←(<4⌽⥊)⎉2 3‿3↕⊢↑ ̋·≍⟜¬2+≢⋄x≡◶S‿0x∧ ́¬(F<≡ ̈(x(F ̈0=1↓ ̈W)∘≥⚇1G{xS⍟≢(⌈ ×ばつ⊑) ×ばつ⌾⥊0=x)∧ ̈<) ̈⊸/Gx}(⍷∘⥊= ̈<)

Try it here.

Fairly unsophisticated method: it flood fills the solved cells to find disconnected regions, then marks as solved cells where all cells of the same number border the edge or a single solved region, then repeats until all cells are solved, or the input no longer changes.

(削除) Can definitely be golfed a lot more. In particular, I think it could probably be rewritten to avoid having to use rank 2 (⎉2) everywhere. (削除ここまで)

Edit: rewrote to use each ( ̈) instead of rank when possible and some other tweaks. Still a few parts I'm convinced can be improved, but I think ultimately trying a completely different approach would be better.