Este desafío se basa en el juego Layerz.

Dado, en stdin o como argumento de función, una matriz rectangular 2D de celdas donde cada celda contiene un espacio en blanco (puede optar por usar 0s en lugar de espacios en blanco sin penalización), un 1, un 2, un 3 o un 4 ; encuentre una manera de dividirlo en regiones válidas (como se define a continuación) de modo que cada celda no vacía esté contenida exactamente por una región. Luego, envíe la solución encontrada en cualquier formato razonable. Si no hay solución, deténgase sin producir salida o dé un solo valor de falsey y luego deténgase.

Cualquiera de los siguientes constituye una región válida:

• Una sola celda que contiene un 1
• Una celda que contiene un 2 y exactamente uno de sus vecinos ortogonales no en blanco
• Una celda que contiene un 3 y exactamente dos de sus vecinos ortogonales no en blanco
• Una celda que contiene un 4 y exactamente tres de sus vecinos ortogonales no en blanco

Este es el código de golf , por lo que la respuesta válida más corta, en bytes, gana.

Algunos casos de prueba:

1. Una bastante trivial:

Y esta es la solución, con cada región en un color diferente:

2. Una más interesante

Esta tiene más de una solución, pero esta es una de ellas:

3. Una más pequeña, que contenga espacios en blanco, que no tenga ninguna solución (dependiendo de si usas una de las dos para "capturar" las tres, o las tres para tomar dos de las dos, te queda un par de dos no adyacentes [y por lo tanto no agrupables] o un solo dos por sí solo):

Debido a que esta grilla no tiene soluciones, su programa debería detenerse sin producir ningún resultado cuando se le da esta grilla.

4. Sin embargo, esta (con los 2 primeros desplazados una celda a la izquierda) tiene una solución:

Solución:

(La parte inferior derecha 2 se usa para "capturar" la 3)

5. Porque necesitábamos un caso de prueba con cuatro patas:

Una solución:

Sé que este desafío tiene más de un año, pero acabo de encontrarlo en "sin respuesta" y me pareció bastante interesante.

Suponiendo que el número de la celda "raíz" es el único significativo en cada región (deducible de los ejemplos), aquí está mi solución de retroceso:

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)

Pruébalo en línea!

El formato de entrada es una lista 2D de enteros, espacios en blanco como cero, y el formato de salida también es una lista 2D de enteros que representan una región por número. El número de región comienza en uno; cero está reservado para celdas en blanco (como en la entrada). Si la entrada dada no se puede resolver, la función devuelve un solo cero (valor falso).

Por ejemplo, el caso de prueba 5 se ingresa como

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

y la salida es

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

Sin golf, con comentarios:

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)
 

Pruébalo en línea!

Nota: Este es un caso especial de Set Packing que se sabe que es NP-complete. Este problema específico tiene un tamaño de conjunto limitado (máx. 4) y existen algoritmos de aproximación para encontrar el empaque de conjunto "bueno" en tiempo polinómico, pero no garantizan el empaque de conjunto máximo posible (que es estrictamente necesario en este problema).