Group these cells!

I know this challenge is over an year old, but I just found this in "unanswered" and looked quite interesting to me.

Assuming that the "root" cell's number is the only significant one in each region (deducible from the examples), here is my backtracking solution:

Python 3, 355 351 349 bytes

from itertools import*
def f(a):
 D=len(a[0])+1;S={D*r+c for r in range(len(a))for c in range(D-1)if a[r][c]};s=[{x,*t}for x in S for t in combinations({x-D,x-1,x+1,x+D}&S,a[x//D][x%D]-1)]
 def B(s,S,d=1):
  if{0}>S:return a
  if[]==s:return 0
  h,*t=s
  if h<=S:
   for x in h:a[x//D][x%D]=d
  return h<=S and B(t,S-h,d+1)or B(t,S,d)
 return B(s,S)

Try it online!

The input format is a 2D list of integers, blanks as zero, and the output format is also a 2D list of integers representing one region per number. The region number starts at one; zero is reserved for blank cells (as in input). If the given input is unsolvable, the function returns single zero (falsy value).

For example, the test case 5 is input as

[[2,3,2],
 [3,4,3],
 [0,4,0],
 [3,3,3],
 [2,3,2],
 [0,3,0]]

and the output is

[[1,1,1],
 [2,2,2],
 [0,2,0],
 [3,4,5],
 [3,4,5],
 [0,4,0]]

Ungolfed, with comments:

from itertools import*
def f(a):
 # Rows, cols, fake-cols to prevent neighbors wrap around
 R,C=len(a),len(a[0]);D=C+1
 # All valid cells represented as integers
 S={D*r+c for r in range(R) for c in range(C) if a[r][c]}
 # All valid regions rooted at each cell
 s=[{x,*t} for x in S for t in combinations({x-D,x-1,x+1,x+D}&S,a[x//D][x%D]-1)]
 # Start backtracking
 return backtrack(a,s,S,D)

# a: array to fill in the region numbers
# s: current candidates of regions
# S: current remaining cells to cover
# D: constant from f
# d: recursion depth == group number in the result
def backtrack(a,s,S,D,d=1):
 # Empty S: the board is correctly covered, return the result
 if not S:return a
 # Empty s: no more candidate regions to use, return false
 if not s:return 0
 h,*t=s
 # h is not a subset of S: h is not a valid cover, try with the rest using same depth
 if not h<=S:return backtrack(a,t,S,D,d)
 # h is a valid cover, write d to the cells in h
 for x in h:a[x//D][x%D]=d
 return backtrack(a,t,S-h,D,d+1)or backtrack(a,t,S,D,d)
 

Try it online!

Note: This is a special case of Set Packing which is well-known to be NP-complete. This specific problem has limited set size (max. 4) and there exist approximation algorithms to find "good" set packing in polynomial time, but they don't guarantee the maximum possible set packing (which is strictly required in this problem).

APL (Dyalog Unicode), 94 bytes

⎕CY'dfns'
{0≡a←X⊢b←⊃⍪/{v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x←v∩⍵(+,-)↓0 2⊤⍳2]}∘⊂¨v←⍸×w←⍵:0⋄(b+.×⍨a×+\a)@v⊢w}

Try it online!

-4 bytes thanks to @Adám. Improvements are:

• x←...⋄...cmat≢x → ...cmat≢x←... (-2 bytes)
• (+\×⊢)a → a×+\a (-2 bytes)

---

APL (Dyalog Unicode), 98 bytes

⎕CY'dfns'
{0≡a←X⊢b←⊃⍪/{x←v∩⍵(+,-)↓0 2⊤⍳2⋄v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x]}∘⊂¨v←⍸×w←⍵:0⋄(b+.×⍨(+\×⊢)a)@v⊢w}

Try it online!

Well, who would have imagined a language having Knuth's Algorithm X as a built-in library function? Algorithm X is an algorithm designed to solve Exact Cover problems, and the challenge here is exactly this kind of problem.

Now it just becomes a matter of constructing the constraint matrix (a boolean matrix whose columns represent constraints and rows represent actions that satisfy some of the constraints). Then X solves the problem by finding the collection of rows so that 1 appears exactly once per column.

Ungolfed with comments

⎕CY'dfns'  ⍝ Load `cmat` and `X`
f←{
  ⍝ v←Coordinates of nonzero positions
  v←⍸×w←⍵

  ⍝ Given an enclosed coord, generate constraint rows
  Rowgen←{
    ⍝ Extract 4-way neighbors that are part of the board
    x←v∩⍵(+,-)↓0 2⊤⍳2
              ↓0 2⊤⍳2  ⍝ Fancy way to say (0 1)(1 0)
        ⍵(+,-)         ⍝ Input coord plus/minus 1 horizontally/vertically
      v∩               ⍝ Set intersection with valid coords

    ⍝ Boolean matrix where each row represents a possible tile placement
    ⍝ and 1 marks the covered cells by that tile
    v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x]
             (w[⍵]-1)cmat≢x   ⍝ Possible combinations of neighbors
         ⍵,x[              ]  ⍝ Index into x and prepend ⍵
    v∊⍤1⊢                     ⍝ Mark covered cells as 1
  }

  ⍝ bmat←Constraint matrix; vertical concatenation of constraint rows
  bmat←⊃⍪/Rowgen∘⊂¨v

  ⍝ ans←Solution by Algorithm X
  ans←X bmat

  ⍝ Return 0 if answer not found (single zero)
  0≡ans:0

  ⍝ Mark the pieces as distinct integers starting from 1
  ⍝ (increasing in the order of the root cell)
  (bmat+.×⍨(+\×⊢)ans)@v⊢w
           (+\×⊢)ans       ⍝ Assign distinct numbers to 1 bits
                           ⍝ 1 0 0 1 0 1 1 .. → 1 0 0 2 0 3 4 ..
   bmat+.×⍨                ⍝ Extract associated numbers for all valid cells
  (                 )@v⊢w  ⍝ Overwrite valid cells of w with ^
}