Witness My Challenge (Tetris Puzzle)
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&lt;=x+d&lt;=w and 0&lt;=y+e&lt;=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&lt;=X&lt;w and 0&lt;=Y&lt;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&amp;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('-&gt;');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)-&gt;(2,1)
(0,0)(0,1)-&gt;(0,1)
(0,0)-&gt;(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)-&gt;(0,0)
(0,0)(1,0)(0,3)(1,3)-&gt;(2,1)
(0,0)(1,0)(2,0)-&gt;(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)-&gt;(1,0)
(0,0)(1,0)(2,0)-&gt;(1,6)
(0,0)(0,1)(0,2)-&gt;(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 |
|* *** ***      |
=================