Witness My Challenge (Tetris Puzzle)

Question

Introduction

In the game The Witness (possible spoilers ahead) there is a group of puzzles that involve drawing a Tetris piece with your line while making sure that the symbol for the Tetris piece your currently drawing stays contained within the shape you've drawn.

For the image above the drawing works because the L-shaped and upside down L-shaped Tetris pieces, occupying the positions (1,2)(2,2)(3,2)(3,3) and (1,1)(1,0)(2,0)(3,0) respectively, and the icons, located at (3,0) and (3,3), are contained within the white line.

Challenge

Your goal is to draw the solution line such that it contains all Tetris pieces as well as their respective symbols. The solution line may not contain anymore squares than that which is required (i.e. you must contain the sum of the number of squares making up each Tetris piece). Each solution will begin in the bottom left and end in the top right. Lastly, this is code-golf, so the shortest solution (in bytes) wins.

Representation

Each of these puzzles use a HxW grid of squares to construct your Tetris pieces and have some space for you to draw lines in between them. The representation is best understood by example. For the above image the representation would be

===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

and the solution would be

===========
|*********|
|*X X X X |
|*******  |
| X X X*X |
|  *** *  |
| X*X*X*X |
|  * * ***|
| X*X*X X*|
|*** *****|
===========

where each square is represented by an X and the solution is drawn using a line of *s. The number of lines for each puzzle is 2*H+3 and the number of characters for each line is 2*W+3.

Input

The first n lines will give you the Tetris piece followed by the location of the corresponding symbol for that Tetris piece. The format is as follows:

(i1,j1)(i2,j2)...(ik,jk)->(p,q)

where (ik,jk) is the kth coordinate pair of the Tetris piece (the left coordinate increases as you move down, the right coordinate increases as you move right) and (p,q) is the location of the corresponding symbol. The origin of each Tetris piece is the top left square (i.e. the top left square is (0,0)).

Example 1:

X
X
XX

would be

(0,0)(1,0)(2,0)(2,1)

Example 2:

XX
X
X

would be

(0,0)(1,0)(2,0)(0,1)

Example 3:

X  X
X  X

would be

(0,0)(1,0)(0,3)(1,3)

The next 2*H+3 lines will consist of the puzzle's grid.

Output

Output the puzzle grid with the solution line drawn in.

Examples

Example Input 1

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

Example Output 1

=========
|*******|
|*X X X |
|*******|
| X X X*|
|***** *|
|*X X*X*|
|*   ***|
=========

Example Input 2

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

Example Output 2

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

Example Input 3

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

Example Output 3

=================
|***         ***|
|*X*X X X X X*X |
|* *******   *  |
|*X X X X*X X*X |
|* *******   *  |
|*X*X X X X X*X |
|* ***********  |
=================

Clarifications

• It is assumed that for any given input there is a solution.
• If there are multiple solutions just print one.

Answer 1

Python, 992

Takes input from stdin and prints the solution. Note that SE has turned my tab characters into four spaces - anything indented beyond one space should be a tab.

It shouldn't be too hard to beat this, but I thought I'd post it since no one else had posted a solution.

L=len
R=range
j=[(-1,0),(1,0),(0,-1),(0,1)]
P=lambda y,x,q:(y,x)==(0,w)and[q+[(y,x)]]or sum([P(y+e,x+d,q+[(y,x)])for e,d in j if not(y+e,x+d)in q and 0<=x+d<=w and 0<=y+e<=h],[])
def C(q,y,x,v):
 if(y,x)in v:return
 v.add((y,x))
 for e,d in j:
    Y,X=y+e,x+d;a,b=[(y+(e+s*d+1)/2,x+(d+s*e+1)/2)for s in[-1,1]]
    if 0<=X<w and 0<=Y<h and not(a in q and b in q and abs(q.index(a)-q.index(b))==1):C(q,Y,X,v)
def G(s,c):
 if not s:return not c
 for y,x in r:
    p=set((Y+y,X+x)for Y,X in s[0])
    if c&p==p and G(s[1:],c-p):return 1
def B(q):
 for y,x in r:
    c=set();C(q,y,x,c);s=[h for(w,h)in p if w in c]
    if s and not G(s,c):return 1
h,p,g=0,[],[]
try:
 while 1:
    s=raw_input()
    if'('in s:l,o=s.split('->');p.append(map(eval,[o,'('+l.replace(')','),')+')']))
    else:g.append(list(s))
except:h=L(g)/2-1;w=L(g[0])/2-1
r=[(x/w,x%w)for x in R(w*h)]
for s in P(h,0,[]):
 if not B(s):break
for(a,b),(c,d)in zip(s,s[1:]):g[1+2*a][1+2*b]=g[1+a+c][1+b+d]=g[1+2*c][1+2*d]='*'
print'\n'.join(''.join(r)for r in g)

Quick rundown of how it works:

P finds all possible paths.

C finds all the squares that are connected to a given square.

G determines whether or not a set of shapes fit exactly in a set of squares.

B determines whether or not a path is bad by checking each connected set of squares and checking if their shapes fit.

Examples

input:

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

output (all tetris pieces are grouped into the top-right):

=========
|***   *|
|*X*X X*|
|* *   *|
|*X*X X*|
|* * ***|
|*X*X*X |
|* ***  |
=========

input:

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

output (this is the only one that's the same as the example solution):

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

input:

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

output (rightmost 2 pieces are grouped together):

=================
|*** *** *******|
|*X*X*X*X*X X X |
|* * * * *******|
|*X*X*X*X X X X*|
|* * * * *******|
|*X*X*X*X*X X X |
|* *** ***      |
=================