I have a 9-piece puzzle which (now, at last) takes me an hour to do - and most people I offer it to can't get it out at all. It's a plain colour, and the shapes are curved without any knobs. No clues from colour or piece shape. Once it's assembled there's a silhouette of a whale INSIDE an irregular coloured border.

How small can a puzzle be if it's to be virtually unsolvable, i.e. if trial and error is the only possible method?

Depends on patience I suppose.

With n pieces, there are n! arrangements they can be in. If they are identical polygons, they can cover the field of they are all rectangles (two ways to place them, long side up or down) triangles (three angles), squares (four), or hexagons (six), unless one gets really exotic. I'll assume that the whale puzzle of yours consists of a 3 x 3 grid of squares, so there are 9! x 4^9 = 95,126,814,720 different ways to put it together, four of which form the picture of a whale (facing up, down, left, right). If you are really handy do go through those positions at a rate of one per second, that's about three thousand years.

The 6,144 positions of a 2x2 grid would take less than two hours at the same pace.. still doable. So I'd say.. a 2x3 grid is the smallest that I would consider "virtually unsolvable". Working at that 24/7 at a rate of one arrangement per second would take roughly one month.

Originally posted by talzamir
I'll assume that the whale puzzle of yours consists of a 3 x 3 grid of squares, so there are 9! x 4^9 = 95,126,814,720 different ways to put it together, four of which form the picture of a whale (facing up, down, left, right).

The puzzle doesn't actually work like that. The pieces are irregular and curved, with two straight equal-length edges randomly located. The idea is to butt the straight edges together with those on other pieces. If you get the sequence right the last two edges left will be in a position adjacent to each other. You don't know you've got it right until almost then, because there's no picture until you have a continuous inner edge to form it.

So it's probably something like: start with edge 1 of piece A, one of the edges on one of the other 8 pieces will match it, so 1 in 16 to get the correct piece B. Then the remaining edge of piece B is looking for a match among 7 pieces, so 1 in 14.
1/16 x 1/14 x 1/12 x 1/10 x 1/8 x 1/6 x 1/4 x 1/2 which makes 10,321,920
possible placings. At the rate of one per second, that's 120 days, not bad for a 9-piece puzzle. Luckily it came with a staged solution, and now I can recognise enough of the pieces to get it out in an hour or two - but for a first-timer without the solution slip, it isn't practically possible. 9 pieces ...