Solving a "Ubongo"-puzzle Some time ago I came across a game called Ubongo. The player got four shapes and has to put them together in a way, that the shapes form the shape of the board. One example is this:


Note that the shapes can be turned or rotated.
Your goal is to write a programm that takes the board and the 4 shapes as parameter (command line or user input, handle it your way) and prints the solution (a graphical solution or a human-readable solution).

Example (same as above):
Input (board size, board information (0 for nothing, 1 for board field), 4x shape size and shape information (same as board information)):  

&gt;myprogram
5 5
11000
11000
11101
11111
00111
2 4
10
10
11
10
1 2
1
1
2 3
01
11
01
2 3
01
11
11


Output:

12000
12000
11304
13344
00344


(0 stands for nothing, 1 for the first shape given in the input, 2 for the second shape etc.)
Note that the choice of input and output is completely free, it should just be easy to understand.

The winner will be crowned two weeks from when the question was posted. The winner will be the person with the least code length.

EDIT :
You can assume that there is a solution to the given board and pieces. If there is no solution, your program does not have to work (but it would be nice if it prints an error message). For those, who need more tests, I found solutions to several puzzles with several boards and pieces here.
Python 2.x - 679 543 443 417 406 383 372 361 bytes

I'm actually pretty sad about this one. I am sure I missed something obvious. I'll be looking at this again later. Starting to feel good about this one.

543 - Edit 1: Discarding efficiency in favor of code length.
443 - Edit 2: Made the algorithm a lot simpler, fixed it (it couldn't handle flips) and
              removed ungolfed code because it wasn't relevant anymore.
417 - Edit 3: Rotate was only being used once anymore. Inlined it. Something else too.
406 - Edit 4: Made it accept only four shapes, as the spec says. Also reduced efficiency again.
383 - Edit 5: Ultimate abuse of exec. Shorter code and longer execution time!
372 - Edit 6: Every recursion now makes a copy of the current board, which is removed if
              the pieces don't fit. No more master board and no more emptying placed pieces.
361 - Edit 7: Removed unnecessary stuff. Also added the byte counts to changelog.




(q,g),O,s=input()
O=[x*6for x in sum(O,[])]
A='z,k=s[i];'+('z,k=z[::-1],zip(*k[::-1]);r=r or c(i+1,z,k,O);'*4+'k=map(reversed,k);')*2
def c(i,(w,h),p,o,r=0):
 for x in range(g*q):O=o[:];f=1;I=0;exec"P=x+I/w*q+I%w;exec('f=0','O[P]=i')[g*q&gt;P&gt;=0and O[P]&gt;4]*p[I/w][I%w];I+=1;"*w*h;exec(i&lt;4*f)*A;r=O*(i*f&gt;3)or r
 return r
i=r=0;exec A+'print`r[i:i+q]`[1::3];i+=q;'*g


It takes the input in an array format. Example:

In:  [5,5],[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,0]]],[[1,2],[[1],[1]]],[[2,3],[[0,1],[1,1],[0,1]]],[[2,3],[[0,1],[1,1],[1,1]]]]
Out: 12000
     12000
     11304
     13344
     00344

In:  [6,5],[[0,1,1,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0],[0,1,1,1,1,0],[0,0,1,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,1]]],[[3,3],[[1,1,0],[0,1,1],[0,1,1]]],[[3,3],[[0,0,1],[1,1,1],[1,0,0]]],[[2,4],[[0,1],[1,1],[0,1],[0,1]]]]
Out: 033110
     223110
     223310
     022410
     004444 (thanks, edc65)


Quick explanation, if you can't read it. The function checks every possible position for a piece. Whenever the piece fits, it recursively checks that all other pieces fit too. When all pieces fit, the board is filled (pieces are placed on the board when checking) and it can be outputted straight away.