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:
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!