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

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

• Can we assume that the input is guaranteed to be solvable? Jun 6, 2014 at 17:02
• @m.buettner Updated the challenge to code-golf only. But I still would like to add a bonus for esoteric programming languages. Any ideas for that? Also, the input should be solveable, because in the game you assume that too. Jun 6, 2014 at 17:04
• Can I take the input in array format? The example would be [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]]] Jun 6, 2014 at 17:22
• @Sirac If you want to add a bonus for esoteric programming languages, you'll need to change the tag to code-challenge. But I personally like this as a plain code golf. The terse esoteric languages are favoured here anyway. Jun 6, 2014 at 17:26
• Jun 6, 2014 at 18:25

Python 2.x - 679 543 443 417 406 383 372 361 bytes

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+'printr[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.

• Nice code. And totally unfathomable to me. Jun 13, 2014 at 1:50
• Thanks! I'm just abusing exec to build loops by multiplying pieces of code, Jun 13, 2014 at 6:39

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.

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

• There might be some places where it can be golfed further. Maybe I can post an updated version tomorrow. Jun 6, 2014 at 19:11
• That output is sweet. Jun 6, 2014 at 22:27

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

• Thanks for the additional test case. Also, that code creeps me out. Jun 9, 2014 at 18:40
• @TheRare de nada. The pseudo code is simple: try to put a shape, the board change, try next ... (like yours) Thinking about a different implementation though Jun 9, 2014 at 23:07
• You passed me! Guess I have some work to do. ;) Jun 11, 2014 at 21:45
• Aaaand you won. Jun 12, 2014 at 9:22
• @TheRare Don't give up! I feel there is room for improvement using single dimension arrays (every two loops become one). Jun 12, 2014 at 10:23