# Group these cells!

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 , 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:

• It would be helpful if there were ASCII versions of the test cases so people don't have to type them all up, and the test cases should also cover 4s if those are valid input. – Martin Ender Nov 23 '16 at 12:12
• does orthogonal neighbors means only left right up down, or also the diagonals? if only left right up down, how come the 3 is in the same region as the other two 3's? one of them is not an orthogonal neighbor. – Eyal Lev Nov 23 '16 at 15:50
• @EyalLev Only left-right-up-down. The top right 3 and its 2 neighbors constitute the region. – SuperJedi224 Nov 23 '16 at 20:15
• @SuperJedi224 the top right 3 and it's two neighbors constitute a valid region, yes, but those neighbors do not. doesn't a region have to be a "closed set"? i.e. every member in the region must be a valid member of that region? – Eyal Lev Nov 27 '16 at 11:35

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, 355351 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]]


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

⎕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