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:
(The bottom right 2 is used to "capture" the 3)
5. Because we needed a test case with some fours: