El juego

Recientemente, gran parte de mi tiempo ha sido ocupado por un juego adictivo en mi teléfono, llamado Logic Dots, que me inspiró a escribir este desafío. Es más fácil explicar las reglas si te muestro la pantalla del juego, así que aquí hay una captura de pantalla de un rompecabezas sin resolver y resuelto:

Ahora aquí, hay tres cosas principales a tener en cuenta.

1. El tablero de juego (la cuadrícula de cuadrados de 4x4 en el centro)
2. Las formas requeridas (los puntos vinculados en la segunda barra desde la parte superior, debajo de la partitura y el menú, etc.), que son todas líneas, o apor 1 rectángulos
3. Los números sobre las filas y columnas, que indican cuántos puntos deben estar en la columna, para una solución

El objetivo del juego es ajustar las formas requeridas en la cuadrícula. Puede rotar las formas, pero no pueden entrar en diagonal.

En la solución, observe que todas las formas se crean exactamente una vez (porque solo están en las formas requeridas una vez), y en este caso son todas horizontales pero también pueden ser verticales. Los cuadrados rellenos de color rosa indican cuadrados no utilizados.

Aquí hay una cuadrícula más grande y un poco más complicada:

Observe que en el rompecabezas sin resolver, ya hay algunos cuadrados rellenados. Los cuadrados en gris significan cuadrados bloqueados en los que NO PUEDE colocar un punto. Los puntos con colas le indican que hay un punto en ese punto, y se vincula con al menos un punto más en la dirección de la cola, pero no en cualquier otra dirección (incluida la dirección opuesta).

Notación

Para el resto de esta publicación, me referiré a la pizarra usando los siguientes símbolos:

• <,>, ^, v - Significa un punto colocado previamente con una cola que se extiende en la dirección del punto
• * - Significa un punto. Si se proporciona en una cuadrícula sin resolver (entrada), es una forma individual. Si está en la salida, entonces está conectado a los puntos a su alrededor.
• #: Significa un cuadrado de cuadrícula bloqueado (donde no puede colocar un punto)
• -, | (guión y barra): significa un punto con una cola derecha e izquierda, y un punto con una cola hacia arriba y hacia abajo respectivamente
• ** (carácter de espacio) - ** Significa un espacio vacío

Usando estos símbolos, el último caso de ejemplo (sin resolver) se puede representar de la siguiente manera:

 <    



    # 
 ^ #

Y la solución se puede representar como:

*< * *
   *  
     *
 *   *
 * *#*
 ^ # *

Tenga en cuenta que no hay dos formas que puedan tocarse horizontal, vertical o diagonalmente , por lo que el siguiente caso no es válido:

 *** 
**   
  ** 

Desafío

Su desafío es resolver cualquier rompecabezas de puntos lógicos, desde 4x4 hasta 9x9 inclusive. Recibirá cuatro líneas de entrada, luego el tablero de juego. Las líneas serán las siguientes:

• Primera línea, Formas: las formas a buscar, cada una dada en la forma sizexquantity(por ejemplo, 3x2para dos formas de longitud tres) y separadas por un espacio. Línea de ejemplo:3x1 2x1 1x1
• 2da línea, Columnas: una lista separada por espacios del recuento de puntos requerido para cada columna. Línea de ejemplo:1 1 2 2
• Tercera línea, Filas: una lista separada por espacios del recuento de puntos requerido para cada fila. Línea de ejemplo:3 0 3 0
• 4ta línea, tamaño de la placa: un número entero único, el tamaño de la placa, B

Luego se da el tablero, y son Blíneas de entrada que representan el tablero usando la notación mencionada anteriormente. Por ejemplo, la entrada completa para el último caso de ejemplo es la siguiente:

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

Su programa generará la placa resuelta, en la misma notación. La salida correspondiente para la entrada anterior es la siguiente:

** * *
   *  
     *
 *   *
 * *#*
 * # *

Tenga en cuenta que un tablero de juego puede tener múltiples soluciones. En este caso, solo genera una solución válida. Además, su programa debe generar una solución correcta en 10 segundos en una computadora de escritorio razonable para una cuadrícula complicada de 10x10.

Este es el código de golf, por lo que gana menos bytes.

Casos de prueba

Entrada 1

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

Salida 1

*** *

 ***#
  #  
* * *

Entrada 2

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 

Salida 2

* * *
  *  
  * *
*  # 
  * *

Entrada 3

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

Salida 3

#     
 *****

 **** 
 #    
* ** *

Python 2: 766 739 696 663 633 bytes

def f(B,S,o=0):
 if[]==S:print'\n'.join(B);exit()
 s=S[0]
 for i in r:
  for j in R(Z-s+1):
   if(B[i][j]in' '+'>v'[o])*(B[i][j+s-1]in' '+'<^'[o])*({' ','-|'[o]}>=set(B[i][j+1:j+s-1]))*all(B[x][y]in'# 'for x,y in [(x,y)for y in R(j-1,j+s+1)for x in i-1,i+1]+[(i,j-1),(i,j+s)]if 0<=x<Z>y>=0):q=B[:];q[i]=q[i][:j]+'*'*s+q[i][j+s:];q=(q,t(q))[o];any((t(q)+q)[k].count('*')>m[k]for k in R(Z+Z))or f(q,S[1:])
 o or f(t(B),S,1)
y=raw_input;S=[];s=str.split
for i in s(y()):u,v=map(int,s(i,'x'));S+=[u]*v
m=map(int,s(y())+s(y()));Z=input();R=range;r=R(Z);B=[y()for _ in r];J=''.join;t=lambda x:map(J,zip(*x))
f(B,S[:len(S)-J(B).count('*')])

Véalo trabajando en línea: Ideone.com (la versión en línea puede ser demasiado lenta para cuadrículas grandes y difíciles, sin conexión debería estar bien)

La entrada es a través de stdin, solo copie y pegue las líneas desde el OP (pero tenga cuidado, stackexchange a veces elimina espacios o líneas).

Algunas ideas básicas de este código: utiliza una función recursiva f. fintenta colocar una forma en el tablero. Para cada ubicación posible se llama a sí mismo con el tablero modificado. Hay 3 bucles en él. odetermina la orientación (2 - horizontal, 3 - vertical). Siempre colocará la forma horizontal, por lo tanto, al final de o=2, transpondrá la placa con la función t. ies la fila y jtodas son posibles columnas iniciales. Luego ocurren muchas comprobaciones, si los extremos de la forma tienen caracteres válidos, si el medio de la forma tiene caracteres válidos y si el entorno está vacío.

JavaScript (ES6) 661 667 695 702 745 755 786 790 784 798

Trabajo en progreso, se puede acortar. Probablemente demasiado lento en una cuadrícula compleja. Tal vez no.

Editar Un poco más, mucho más rápido.
Editar 2 Corrección de errores, verificación de columnas / filas. Por cierto, ahora es más rápido

La función M es la principal. El parámetro w es una cadena multilínea con toda la entrada. La función analiza la entrada y prepara una tabla de inicio. Los caracteres <>^v|-*en el tablero inicial se reemplazan con ,, cada uno ,tiene que ser reemplazado con *la solución correcta.

La función R intenta recursivamente colocar todas las formas en el tablero. Cuando se coloca una forma, se llama a sí misma pasando una lista más corta de formas y el tablero modificado. Cuando se colocan todas las formas, una solución aún puede ser inválida si no se ,reemplaza por *.

La función P prueba si se puede colocar una forma en una posición y orientación determinadas. Comprueba todos los costrains (dentro del tablero, sin superposición, sin contacto, recuento válido de filas y columnas)

M=w=>(
  [x,c,r,z]=w=w[S='split'](n='\n'),
  (b=[...w.slice(4).join(n)])
  .map((c,p)=>~(k='*<>-*^v|'.indexOf(c))&&[(q=k>3?z:1,0),k&1&&-q,k&2&&q].map(o=>b[p+o]=0),
    c=c[S](e=' '),r=r[S](e),w=z++,f='*',s='',x[S](e).map(v=>s+=v[0].repeat(v[2]))),
  R=(s,b,x=0,y=0,n=s[0],V=i=>b[i]>'#',
    P=(p,o,q,t,g,l,d=[...b])=>{
        if(l<z-n&!V(p+o*l-o)&!V(p+o*l+o*n))
        {
          for(i=-1;v=d[p],++i<w;p+=o,t-=v==f)
            if(i>=l&i-n<l)
              for(v!=e&v!=0|[q,w,~z].some(w=>V(p+w)|V(p-w))?t=0:d[p]=f,j=o*i,u=k=0;
                  ++k<z;(u+=d[j]==f)>g[i]?t=0:j+=q);
          return t>=n&&d.join('')
        }
    })=>{
    if(b){
      if(!n)return~b.search(0)?0:b;
      for(s=s.slice(1);y<w||(y=0,++x<w);++y)
        if(h=R(s,P(y*z,1,z,r[y],c,x))||n>1&&R(s,P(x,z,1,c[x],r,y)))return h
    }
  })(s,b)

Prueba en la consola FireFox / FireBug

;['3x2 1x4\n2 2 3 1 2\n4 0 3 0 3\n5\n     \n     \n    #\n  #  \n    *\n'
,'3x1 1x6\n2 0 4 0 3\n3 1 2 1 2\n5\n*    \n     \n     \n   # \n     \n'
,'5x1 4x1 2x1 1x2\n1 2 3 3 2 2\n0 5 0 4 0 4\n6\n#     \n  -   \n      \n      \n #    \n   <  \n'
,'4x1 3x1 2x2 1x2\n1 4 0 3 0 5\n4 1 1 2 3 2\n6\n <    \n      \n      \n      \n    # \n ^ #  \n']
.forEach(x=>console.log(x,M(x).replace(/ /g,'`'))) // space replaced with ` for clarity

Salida (tiempo de ejecución total <1 segundo)

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

***`*
`````
`***#
``#``
*`*`*

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 


*`*`*
``*``
``*`*
*``#`
``*`*

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

#`````
`*****
``````
`****`
`#````
*`**`*

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

**`*`*
```*``
`````*
`*```*
`*`*#*
`*`#`*