Solving a Jigsaw Puzzle!
Ruby, 1220

Wow that was something... I didn't think it would take THAT much to make this, but hey, only way to learn was try it. It's clear now why there weren't any answers to the question...

Well, I'm sure this is golfable, but It's been a whole job only to make it. Following is golfed code and then ungolfed with some explanations:

e=[[]]
while(a=gets)
if(a=a.chomp)==""
e.push []
else
e.last.push a.chomp
end
end
e.keep_if{|p|p!=[]}
e.map!{|p|m={}
t=p[0].strip
if t.length==1
m[:t]=t
l=p[1].split" "
b=p[2]
else
m[:t]=nil
l=t.split" "
b=p[1]
end
x=l[0]=~/\d/
m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
m[:b]=b.nil? ? nil:b.strip
m}
w=e.select{|p|p[:t].nil?}.length
h=e.length/w
def c(j,p,l)
x=l[0]
y=l[1]
(x==0&amp;&amp;p[:l].nil?||x!=0&amp;&amp;(j[x-1][y].nil?||j[x-1][y][:r].swapcase==p[:l]&amp;&amp;(j[x-1][y][:v]-p[:v]).abs&lt;2))&amp;&amp;(x==j.length-1&amp;&amp;p[:r].nil?||x!=j.length-1&amp;&amp;(j[x+1][y].nil?||j[x+1][y][:l].swapcase==p[:r]&amp;&amp;(j[x+1][y][:v]-p[:v]).abs&lt;2))&amp;&amp;(y==0&amp;&amp;p[:t].nil?||y!=0&amp;&amp;(j[x][y-1].nil?||j[x][y-1][:b].swapcase==p[:t]&amp;&amp;(j[x][y-1][:v]-p[:v]).abs&lt;2))&amp;&amp;(y==j[0].length-1&amp;&amp;p[:b].nil?||y!=j[0].length-1&amp;&amp;(j[x][y+1].nil?||j[x][y+1][:t].swapcase==p[:b]&amp;&amp;(j[x][y+1][:v]-p[:v]).abs&lt;2))
end
def d(j,q,l)
f=[false,[]]
q.each_index{|i|p=q[i]
if c j,p,l
r=q.dup
r.delete_at i
j2=j.dup
j2[l[0]][l[1]] = p
if r.length==0
f = [true,j2]
break
else
n=l[0]+1
l2=[n%j.length, l[1]+n/j.length]
f = d(j2,r,l2)
break if f[0]
end
end}
f
end
j=[]
w.times{j.push [];h.times{j.last.push nil}}
s=d(j,e,[0,0])
h.times{|y|w.times{|x|print s[1][x][y][:v].to_s+" "}
puts''}


Ungolfed:

pieces=[[]]
while (a=gets) # Read the input and separate by pieces when finding an empty line
  if (a=a.chomp)==""
    pieces.push []
  else
    pieces.last.push a.chomp
  end
end
pieces.keep_if{|p|p!=[]} # Remove possible empty pieces
pieces.map!{|p| # Parse each piece
  m={}
  t=p[0].strip
  if t.length==1
    m[:t]=t
    l=p[1].split" "
    b=p[2]
  else
    m[:t]=nil
    l=t.split" "
    b=p[1]
  end
  x=l[0]=~/\d/
  m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
  m[:b]=b.nil? ? nil:b.strip
  m
}
w=pieces.select{|p|p[:t].nil?}.length
h=pieces.length/w

def fits(j,p,l) # This function determines if a piece fits in an empty spot
  (l[0]==0&amp;&amp;p[:l].nil? || l[0]!=0 &amp;&amp; (j[l[0]-1][l[1]].nil? || j[l[0]-1][l[1]][:r].swapcase==p[:l] &amp;&amp; (j[l[0]-1][l[1]][:v]-p[:v]).abs&lt;2)) &amp;&amp;
    (l[0]==j.length-1&amp;&amp;p[:r].nil? || l[0]!=j.length-1 &amp;&amp; (j[l[0]+1][l[1]].nil? || j[l[0]+1][l[1]][:l].swapcase==p[:r] &amp;&amp; (j[l[0]+1][l[1]][:v]-p[:v]).abs&lt;2)) &amp;&amp;
    (l[1]==0&amp;&amp;p[:t].nil? || l[1]!=0 &amp;&amp; (j[l[0]][l[1]-1].nil? || j[l[0]][l[1]-1][:b].swapcase==p[:t] &amp;&amp; (j[l[0]][l[1]-1][:v]-p[:v]).abs&lt;2)) &amp;&amp;
    (l[1]==j[0].length-1&amp;&amp;p[:b].nil? || l[1]!=j[0].length-1 &amp;&amp; (j[l[0]][l[1]+1].nil? || j[l[0]][l[1]+1][:t].swapcase==p[:b] &amp;&amp; (j[l[0]][l[1]+1][:v]-p[:v]).abs&lt;2))
end

def rec(j,pl,l) # Recursive function to try every piece at every position it can fit
  found = [false,[]]
  pl.each_index{|i|
    p=pl[i]
    if fits(j,p,l) # Try the piece in the spot
      pl2=pl.dup
      pl2.delete_at i
      j2=j.dup
      j2[l[0]][l[1]] = p
      if pl2.length==0 # If we have spent all the pieces, then we have a complete puzzle
        found = [true,j2]
        break
      else             # Keep recurring until we use up all the pieces
        n=l[0]+1
        l2=[n%j.length, l[1]+n/j.length]
        found = rec(j2,pl2,l2)
        break if found[0]
      end
    end
  }
  found
end

j=[]
w.times { j.push []; h.times { j.last.push nil }}
solved = rec(j, pieces, [0,0])
h.times{|y|
  w.times{|x|
    print solved[1][x][y][:v].to_s + " "
  }
  puts ''
}