Produced by means of sophisticated software, or possibly an
idiot savant, a jigsaw puzzle which can be assembled into
either of two completely different pictures.

I assume that you mean both images are printed on the
same side of the puzzle and require assembly in different
configurations, since double-sided jigsaw puzzles have
been around since... well, probably for just a little less
time than single-sided puzzles.

That was indeed my meaning. With a double-sided
puzzle, there's only one way to put the pieces
together, and doing so completes both pictures.
With the dual jigsaw, the same pieces (printed only
one one face) can be assembled in two completely
different ways. The curve of the Mona Lisa's left
eyebrow in one picture becomes the wing of a
seagull in the other - that kind of thing.

Ingenious, but is it possible? Given my usual standpoint
that nothing is impossible until proven so (but that many
things unproven are highly improbable), I'd like to see it
tried. I suspect it would involve massive quantities of
crunchy math. [+]

Ideally, the shapes of the pieces would have to be
such that they all fit together in two, but not
more than two, ways. This constrains the solution
space - if two pieces X, Y fit together because X
has an edge shape A and Y has the edge shape A',
then for these to work in another orientation
implies the existence of pieces P, Q, where P has
an edge shape A and Q has an edge shape A'. So, in
one orientation X and Y fit together and P and Q
fit together, and in the other orientation, X and Q
fit together and Y and P fit together. Thus, any
pair of pieces is linked to another pair of pieces.
However, this implies that all other edges of
these pieces are also 'locked' with those in the
paired pieces so the two pictures represented by
the puzzle can only be those which can be
created by swapping a number of pieces in the
puzzle with other pieces, where each piece can
only be swapped once.

I suspect that this may make finding either solution quite hard. Although it occurs to me that a degenerate solution to the creation problem is one of those pictures of a face which is a different face the other way up.

...

You know how you only really know you arn't missing any pieces when you've finished it and there arn't any missing? My daughter found an interesting counterpart to that the other day. She's just learning how to do them, and doesn't always pay attention to the picture when fitting pieces together.
Imagine my surprise when she finished a puzzle _with_pieces_left_over_!

Basically the designer had repeated the edges for a vertical slice; she'd assembled it without the intervening columns. Even the picture matched up quite well so I had to look for a moment to figure it out.

Yes, doubtless. You might wind up with some
pieces which will physically fit in the "wrong"
place in either version of the puzzle, but (as your
example shows), this happens with regular jigsaws
too, to an extent. I guess you would need a finite
library of nobbles and complementary obnells*,
and assign them by some sort of reciprocal version
of the de Lavier-Mainwaring algorithm.

(*the obnell is the recess in one jigsaw piece into
which the nobble of its neighbour fits.)

//So, in one orientation X and Y fit together and P and Q fit together, and in the other orientation, X and Q fit together and Y and P fit together. Thus, any pair of pieces is linked to another pair of pieces. However, this implies that all other edges of these pieces are also 'locked' with those in the paired pieces so the two pictures represented by the puzzle can only be those which can be created by swapping a number of pieces in the puzzle with other pieces, where each piece can only be swapped once.//

Hippo, I'm not sure I understand what you're saying there. Are you saying that essentially you end up with identically shaped pairs of pieces?
I don't think that's necessarily the case - at least, not if some liberties are taken. Firstly we can take the idea of knobbles on the edges from my 'maximal difficulty jigsaw' idea. Secondly, we could use slightly non-canonical arrangements - for example, arrange for two pieces in one orientation to bracket a knobble.
Besides that we could of course break the ideal that pieces only fit together in two ways, in particular by having flat edges on the inside of the puzzle. Provided the puzzle as a whole has only two solutions I think that would be acceptable.

The de Lavier-Mainwaring algorithm comes from
topology, and specifically from the topology of
interlinked objects. In some such sets, the
topology of one object limits the possible
topologies of those it interlinks with.

Given a large (or infinite but periodic) set of
linked topologies, there are several possibilities.
One is that all the objects are "connected" in such
a way that, if the topology of one is chosen, then
the topologies of all the others are determined
(limited to a single choice).

Another possibility is that there is no "stable
solution" - the relationships are such that
whichever topology you choose for one object, it
determines the topology of the next and the
next... and then this comes full circle and makes
the chosen topology of the first object
impossible.

Yet another possibility (which bears on the
present discussion) is that the "connectedness"
splits the objects into two (never more) groups,
where the members of one group are related to
eachother, yet the two groups are independent of
eachother (a bit like a lot of gears which actually
comprise two independent gear-trains).

The de Lavier-Mainwaring algorithm is actually a
group of analytical techniques for determing
which type of behaviour will be shown by a given
group of objects. It can be applied iteratively to
create a group which behaves in any chosen way.

The jigsaw problem isn't quite the same (it doesn't
involve topology except in a trivial sense), but the
dL-M method should make it possible to derive
(iteratively) a set of relationships between the
puzzle pieces which can be arranged in either of
two different configurations.

de Lavier and Mainwairing were actually only one
person (de Lavier was his first name). There is a
story of his being honoured at a dinner, and
arriving to find two places laid for him - one for de
Lavier and one for Mainwairing. He solved the
problem by eating two dinners.

I think this is possible, but for it to work, you would
have to start with images that are fairly abstract (or
possibly pointilist) or pieces that are extremely
small relative to the finished image. Otherwise it's
going to be extremely difficult to produce a clean
image.

It seem like this would be best implemented as a puzzle with a fairly small number of pieces. Whenever I've complete a 1000 or more piece puzzle, I've never had the urge to tear it apart and re-do it, but with this puzzle you really want to do the puzzle both ways.

In addition, with a huge number of pieces, it basically has to be computer generated and be a very abstract image or possibly very pixilated like those images made of many tiny pictures.

If the number of pieces is small, it seems like this could be created as a hand drawn sketch of similar complexity to those images that can be interpreted differently based on orientation ([Loris]'s degenerate version). It would be very helpful for the artist to have a computer program that displays the image for both completed puzzle configurations and allows editing in both. The software should also have the ability to adjust the shape of the pieces to move bits of the puzzle between different parts of the puzzle as necessary. It would also be useful if the program could dynamically recalculate possible piece layouts, allowing the artist to choose the general vicinity /orientation that would make lines in one image more useful in the alternate image.

I could see 4 piece puzzles made of fine engraved wood that would be perfect for the coffee table or desk. A 48 or 100 piece puzzle could be interesting. It could be like a normal puzzle with regular edge pieces and the completed picture shown on the front of the box except for the statement: "Challenge: assemble this puzzle in an alternate configuration to discover the secret image.” In that case, some straight edges might not be on the edge, and the completed puzzle would not necessarily be rectangular. For that matter, it isn't a hard requirement that pieces have an overall square shape with the typical nobbles/obnells on each side. Of course limiting the types of shapes might simplify the software, but allowing more freedom could give the artist a lot more flexibility and result in more interesting puzzles and images.

//it basically has to be computer generated and
be a very abstract image// I'm not so sure. The
nobble/obnell pattern would probably have to be
computer generated (even using deL-M methods),
but I think a clever artist
could dice the Mona Lisa and rearrange the pieces
into The Haywain.

Obviously, I'm not completely convinced that
even the cleverest artist would be allowed to
actually dice the Mona Lisa. Probably he (or she,
obviously) would be ejected from the Louvre and
would instead have to work with a good-quality
copy. Alternatively, he (or she, obviously) could
start instead with The Haywain, which no
discerning viewer would object to being diced up.

Oh, hang on, it would seem that I'm going mad.
Watch this space.

A halfway idea: a variant on the double-sided jigsaw where each side needs to be assembled in a different configuration to produce the correct picture. Difficulty level depends on how different the pictures are. Do this with two different Monet paintings, and it might be nearly as hard as the single-side dual solution puzzle. [+]

That suggests some form of competitive jigsaw:
two contestants, each with a puzzle, and one pile
of loose pieces shared between them; each
player may take a piece from the pile only if they
can fit it into their own developing puzzle. There
would be some unique pieces in the pile which
both players needed, so strategy would involve
building your puzzle quickly to the point where
you could incorporate these "high value" pieces,
depriving your opponent of them. It should be
possible to construct a range of higher- or lower-
scoring puzzles depending on availability of "good"
pieces. (Enough similarities to other games that it
might already exist. Anybody know?)

Another degenerate case: completely interchangable pieces in several different colours (eg. the stereotypical knobble-obnell-knobble-obnell jigsaw piece). Build any picture you like. Rather a boring solution, although they might make nice wall tiles - if the narrow bits arn't too fragile.

A trivial way of achieving a less exciting version of this would be to follow the MAD magazine duo-fold model, though this would involve having one resulting picture larger than the other, and when completing the smaller version, having leftover pieces.