Solving a "Ubongo"-puzzle

Question

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

>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.

Answer 1

GolfScript, 210 characters

n%{(~\;/(\[]:f*}5*;].,,]zip{~{.!+`\1`/*n*~]}+%}%(:b{,:^1,*}%]({^,{[^1,*:e.@<\]`{\*^<}+1$%:a;b,:h,{[[e]h*.@<\]a*h<}/}%{.zip{.-1%.zip}3*}%.&`{{[[f*1$f*]zip{~+}%b f*]zip{~*}%^/}%~}+@%{1$f*0-.@f*@0={=}+,=},\;}/0=n*

This is a first attempt using GolfScript. Input must be given on STDIN in the same format as the example in the question. The output format results from an implementation error (using ascii values instead of numerics) but I left it in this form because it is short and looks nice.

☺☻
☺☻
☺☺♥ ♦
☺♥♥♦♦
  ♥♦♦

Answer 2

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>P>=0and O[P]>4]*p[I/w][I%w];I+=1;"*w*h;exec(i<4*f)*A;r=O*(i*f>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.

Answer 3

Javascript (E6) 316 350 392 487 537 590

Board size limited to 6x6 to save runtime. With the same character count the limit could be 9x9. Any number of pieces

    F=(d,b,h)=>{R=s=>[...s].reverse(),Q=(n,i,k)=>{h[n]&&[t=h[n][1],t[0].map((c,i)=>t.map(r=>r[i]))].map(e=>[e,R(e),e.map(R),R(e).map(R)].map(s=>{for(i=36;i--;)k=b.map(x=>[...x]),s.some((u,q)=>!(w=b[~~(i/6)+q])||u.some((v,p)=>(c=i%6+p,v&&!(v=w[c]!=1)&&!(w[c]=n+2)||v)))||Q(n+1),b=k}))||console.log(b.join('\n'))},Q(0)}

---

History

316 - Slooower! The board is copied again for each recursive call. (Ab)using slower functions chosen for shorter names. The main loop on board rows and colums coalesced into one for. Also put a limit for board size up to 6x6 (not for short code, but for acceptable runtime)
350 - Golfed using more array traversing function and less loops
392 - Algorithm not changed: try to place a piece, if ok try next, recursive, but use arrays only and not strings and use a single global board and not copy it during recursion (so it must be able to put a piece AND to remove it)
...

Ungolfed a bit

F = (d,b,h)=>{
  R = s => [...s].reverse(), // ... instead of slice that is faster
  Q = (n,i,k) => // Recursive function, fake param i to avoid vars
  {
    h[n] && // If there is still a piece to place, try to place it
    [t=h[n][1], t[0].map((c,i) => t.map(r => r[i]))] 
      .map(e => // for e in :piece, transposed piece
        [e, R(e), e.map(R), R(e).map(R)]
        .map(s => 
          { // for s in : base piece, reversed, mirrored, diagonal
            for(i = 36; i--;) // 6x6: could be higher but slows down
              k = b.map(x=>[...x]), // save copy of board (again ... instead of slice)
              s.some( (u,q) => // traverse with 'some' to exit early if invalid position
                !(w=b[~~(i/6)+q]) 
                || u.some((v,p) => (c=i%6+p, v && !(v=w[c]!=1) && !(w[c]=n+2)||v)) 
              ) || Q(n+1), // if piece place, recurse
              b=k // recover the board from the copy
          }
      )) // if no more pieces, output result
    || console.log(b.join('\n' /** ,Q=_=>0 **/)) // remove comment to stop at first solution found
  },
  Q(0) // First call
}

Usage

Test in javascript console (Firefox) Input parameters as array.

Time to finish is 50 sec on my PC, so Firefox will complain...

F(
[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]]]
])

Another test case:

F(
 [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]]]
 ]
)

Output / 2+2 solutions found, firefox console skip repeated console output

0,2,2,2,2,0
3,3,4,2,2,0
3,3,4,4,4,0
0,3,3,5,4,0
0,0,5,5,5,5

---

0,4,4,2,2,0
3,3,4,2,2,0
3,3,4,4,2,0
0,3,3,5,2,0
0,0,5,5,5,5