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

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=𝔽⥊𝕩?1;W←(<4⌽⥊)⎉2 3‿3↕⊢↑˝·≍⟜¬2+≢⋄𝕩≡◶𝕊‿0𝕩∧´¬(𝔽<≡¨(𝕩(𝔽¨0=1↓¨W)∘≥⚇1𝔾{𝕩𝕊⍟≢(⌈´×·×⊑)¨W𝕩}+`⊸×⌾⥊0=𝕩)∧¨<)¨⊸/𝔾𝕩}(⍷∘⥊=¨<)

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.