Solving a Jigsaw Puzzle!

Question

I've just bought a new jigsaw puzzle but, as a programmer, I'm too lazy to do it by myself. So I've devised a way to encode the pieces, and now I need a way to solve the puzzle itself.

Challenge

A puzzle piece will have from 2 to 4 connecting corners, defined by a letter; and a color, defined by a number.

  a
B 1 c
  D

a 2 b
  C

3 A
b

The challenge is to build the puzzle from the pieces according to the next rules:

• Two pieces may only be adjacent if they have a matching connection in the corner where they are adjacent. If a piece doesn't have a connection in one of the sides, that side is a corner and can't be connected to another piece.

• Lowercase letters are considered indents and uppercase letters are considered outdents. An uppercase letter connects with its lowercase pair.

• The color of 4-adjacent pieces will differ at most by 1.

• Every piece can and has to be used exactly once.

Input

Your program will receive a randomized list of the pieces, separated with newlines, as seen in the examples. The input pieces are in the right direction: you don't need to rotate them (there is a bonus for inputs with rotated pieces, see below).

Output

Your program should output a solution to the puzzle, with columns separated by blank space (space or tab are okay) and rows by newlines. It might not be unique, but only one possible solution is required.

1 2 3 4 3 4 5 4
1 1 2 3 4 4 4 5
2 1 1 2 3 4 5 6
3 2 2 3 4 5 6 7
2 3 3 4 5 6 7 8
3 4 4 5 6 7 8 9
3 4 5 6 7 8 9 10

Scoring

The shortest answer in bytes wins.

Bonus

The generator script provides options to randomize the rotation of the pieces, but since it may become more complex, a 50% bonus is awarded to whoever implements it (that is, your-byte-count * 0.5).

For that case, assume all the tiles in the input will have a randomized rotation, except the first one, which will have the rotation of the original grid (so as to avoid having at least 4 different solutions).

Test Cases

Test cases can be obtained using the following ruby scripts:

https://gist.github.com/rcrmn/2ba23845d65649c82ca8

The first one generates the solution grid. The second one generates the puzzle pieces from it. Note that they have optional arguments, described in each ruby file.

Following is an example. It's here because I made it by hand before writing the generator and I got attached to it:

http://pastebin.com/PA9wZHma

This test case should output:

1 2 3 4
2 3 4 5
3 4 5 6

As usual, common loopholes are not permitted.

Good luck!

Answer 1

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&&p[:l].nil?||x!=0&&(j[x-1][y].nil?||j[x-1][y][:r].swapcase==p[:l]&&(j[x-1][y][:v]-p[:v]).abs<2))&&(x==j.length-1&&p[:r].nil?||x!=j.length-1&&(j[x+1][y].nil?||j[x+1][y][:l].swapcase==p[:r]&&(j[x+1][y][:v]-p[:v]).abs<2))&&(y==0&&p[:t].nil?||y!=0&&(j[x][y-1].nil?||j[x][y-1][:b].swapcase==p[:t]&&(j[x][y-1][:v]-p[:v]).abs<2))&&(y==j[0].length-1&&p[:b].nil?||y!=j[0].length-1&&(j[x][y+1].nil?||j[x][y+1][:t].swapcase==p[:b]&&(j[x][y+1][:v]-p[:v]).abs<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&&p[:l].nil? || l[0]!=0 && (j[l[0]-1][l[1]].nil? || j[l[0]-1][l[1]][:r].swapcase==p[:l] && (j[l[0]-1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[0]==j.length-1&&p[:r].nil? || l[0]!=j.length-1 && (j[l[0]+1][l[1]].nil? || j[l[0]+1][l[1]][:l].swapcase==p[:r] && (j[l[0]+1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[1]==0&&p[:t].nil? || l[1]!=0 && (j[l[0]][l[1]-1].nil? || j[l[0]][l[1]-1][:b].swapcase==p[:t] && (j[l[0]][l[1]-1][:v]-p[:v]).abs<2)) &&
    (l[1]==j[0].length-1&&p[:b].nil? || l[1]!=j[0].length-1 && (j[l[0]][l[1]+1].nil? || j[l[0]][l[1]+1][:t].swapcase==p[:b] && (j[l[0]][l[1]+1][:v]-p[:v]).abs<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 ''
}