Group these cells!

Question

This challenge is based on the game Layerz.

Given, on stdin or as a function argument, a 2D rectangular array of cells where each cell contains either a blank (you may choose to use 0s instead of blanks at no penalty), a 1, a 2, a 3, or a 4; find a way to divide it into valid regions (as defined below) such that each non-blank cell is contained by exactly one region. Then, output the solution found in any reasonable format. If there is no solution, either halt without producing output or output a single falsey value then halt.

Any of the following constitutes a valid region:

• A single cell containing a 1
• A cell containing a 2 and exactly one of its non-blank orthogonal neighbors
• A cell containing a 3 and exactly two of its non-blank orthogonal neighbors
• A cell containing a 4 and exactly three of its non-blank orthogonal neighbors

This is code-golf, so the shortest valid answer, in bytes, wins.

Some test cases:

1. A rather trivial one:

And this is the solution, with each region in a different color:

2. A more interesting one

This one has more than one solution, but here's one of them:

3. A smaller one, containing blanks, that doesn't have any solutions (depending on whether you use one of the twos to "capture" the three, or the three to take two of the twos, you're either left with a pair of nonadjacent [and therefore nongroupable] twos or a single two on its own):

Because this grid has no solutions, your program should halt without producing any output when given this grid.

4. This one (with the top 2 shifted one cell to the left) does have a solution though:

Solution:

(The bottom right 2 is used to "capture" the 3)

5. Because we needed a test case with some fours:

One solution:

Answer 1

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).

Answer 2

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 ^
}