Logical Dot Shapes

Question

The Game

Recently, much of my time has been taken up by an addicting game on my phone, called Logic Dots, which inspired me to write this challenge. It's easier to explain the rules if I show you the game display, so here is a screenshot of an unsolved, and solved puzzle:

Now here, there are three main things to notice.

1. The game board (the 4x4 grid of squares in the center)
2. The required shapes (the linked dots in the second bar from the top, under the score and menu, etc.), which are all lines, or a by 1 rectangles
3. The numbers over the rows and columns, which denotes how many dots need to be in the column, for a solution

The objective of the game is to fit the required shapes into the grid. You can rotate the shapes, but they cannot go in diagonally.

In the solution, notice that all shapes are created exactly once (because they are only in the required shapes once), and in this case they are all horizontal but they can also be vertical. The pink filled in squares denote squares not used.

Here is a bigger, and slightly more complicated grid:

Notice that in the unsolved puzzle, there are already a few squares filled i.n The greyed out squares signify blocked squares that you CANNOT place a dot on. The dots with tails tell you that a dot is in that spot, and it links to at least one more dot in the direction of the tail, but not in any other direction (including the opposite direction).

Notation

For the rest of this post, I will refer to the board using the following symbols:

• <, >, ^, v - Signifies a pre-placed dot with a tail extending in the direction of the point
• * - Signifies a dot. If given on an unsolved grid (input), it is an individual shape. If in output, then it is connected to the dots around it.
• # - Signifies a blocked grid square (where you cannot place a dot)
• -, | (hyphen and bar) - Signify a dot with a right and left tail, and a dot with an up and down tail respectively
• ** (space character) -** Signifies an empty space

Using these symbols, the latter example case (unsolved) can be represented as follows:

 <    



    # 
 ^ #

And the solution can be represented as:

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

Note that no two shapes can touch horizontally, vertically or diagonally, so the following case is not valid:

 *** 
**   
  ** 

Challenge

Your challenge is to solve any logic dots puzzle, from 4x4 to 9x9 inclusive. You will receive four lines of input, then the game board. The lines will be as follows:

• 1st line, Shapes - The shapes to find, each given in the form sizexquantity (eg. 3x2 for two shapes of length three) and separated by a space. Example line: 3x1 2x1 1x1
• 2nd line, Columns - A space separated list of the required dot count for each column. Example line: 1 1 2 2
• 3rd line, Rows- A space separated list of the required dot count for each row. Example line: 3 0 3 0
• 4th line, Board size - A single integer, the board size, B

The board is then given, and is B lines of input representing the board using the notation mentioned above. For example, the complete input for the latter example case is as follows:

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



    # 
 ^ #  

Your program will then output the solved board, in the same notation. The matching output for the above input is as follows:

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

Note that a game board can have multiple solutions. In this case, just output one valid solution. Also, your program must output a correct solution within 10 seconds on a reasonable desktop computer for a complicated 10x10 grid.

This is code golf, so least bytes wins.

---

Test Cases

Input 1

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


    #
  #  
    *

Output 1

*** *

 ***#
  #  
* * *

Input 2

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


   # 

Output 2

* * *
  *  
  * *
*  # 
  * *

Input 3

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


 #    
   <  

Output 3

#     
 *****

 **** 
 #    
* ** *

Answer 1

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('*')])

See it working online: Ideone.com (The online version may be too slow for large and difficult grids, offline it should be fine)

Input is via stdin, just copy and past the lines from the OP (but be careful, stackexchange sometimes deletes spaces or lines).

Some basic ideas of this code: It uses a recursive function f. f tries to place one shape at the board. For each possible location it calls itself with the modified board. There are 3 loops in it. o determines the orientation (2 - horizontal, 3 - vertical). It will always place the shape horizontal, therefore at the end of o=2, it will transpose the board with the function t. i is the row and j are all possible starting columns. Then a lot of checks happen, if the ends of the shape have valid chars, if the middle of the shape has valid chars and if the surrounding is empty.

Answer 2

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

Work in progress, can be shortened. Probably too slow on a complex grid. Maybe not.

Edit A bit longer, a lot faster.
Edit 2 Bug fix, columns/rows check. Incidentally, now it's faster

The M function is the main. The w parameter is a multiline string with all the input. The function parses the input and prepare a starting board. Characters <>^v|-* in the starting board are replaced with ,, each , has to be replaced with * in the correct solution.

The R function tries recursively to place all shapes in the board. When a shape is placed, it calls itself passing a shorter list of shapes and the modified board. When all shapes are placed, a solution can still be invalid if there are , not replaced by *.

The P function test if a shape can be placed a a given position and orientation. It checks all the costrains (inside the board, no overlap, no touch, valid row and column count)

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)

Test In FireFox/FireBug console

;['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

Output (total execution time < 1sec)

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
 <    



    # 
 ^ #  

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