in reply to Do you suffer "Jigsaw rage"?

I was very disappointed to read the article, because the words used in the quotation "construct a jigsaw" are at odds with the desired meaning. :-(

No one actually built their own jigsaw(an interesting feat of electrical and mechanical engineering). They didn't even build their own jigsaw puzzle (which is what I expected the article refered to). They just assembled a pre-existing jigsaw puzzle out of existing puzzle pieces. Children (and the jumbo sized version, called 'adults') have fought over "the right" way to play the puzzle game for years. I was disappointed to find little new in the article that direct experience in my childhood didn't already tell me.

As someone who is mostly interested in Perl programming, (rather than human psychology as applied to Perl programmers), let me instead pose a different puzzle question: How could one write an efficient perl program to solve a jigsaw puzzle? Given a representation of the pieces (say, scanned images), and a representation of the final result, how do you avoid "combinatorial explosion" in the number of comparisons required?

As a more challenging variation, simulate some human limitations. Unlike computers, humans can't tell at a glance whether a given "sky coloured" puzzle piece with two knobs and an edge matches in a given place without picking it up, and trying it for fit. You could simulate something similar for the computer: give colour information about the piece within a given rgb range, and "fuzzy" rather than exact edge configuration information. Moving a piece into a slot would give some limited information about the quality of the match (fits exactly, fits badly, nearly fits, etc). Minimize for (a) amount of time to solve the puzzle, and/or (b) number of pieces "moved". Assign a higher 'time cost' to moving a piece, given that moving a piece is slower than thinking about a piece, to an extent.

To make it all Perl related, submit your solution in Perl (or post to cpan as a puzzle solver).

Best of luck to anyone brave enough to attempt such a program! :-)

--
Ytrew Q. Uiop

Replies are listed 'Best First'.
Re^2: Do you suffer "Jigsaw rage"?
by trammell (Priest) on Jan 02, 2005 at 23:55 UTC
    How could one write an efficient perl program to solve a jigsaw puzzle?

    Step one would probably be to do the border. :-)

    Seriously though, take a look at Picking Up the Pieces a /. article about "unshredding" documents.

[reply]
Re^2: Do you suffer "Jigsaw rage"?
by CountZero (Bishop) on Jan 02, 2005 at 20:56 UTC
    I think a software jigsaw solver would be quite easy (at least conceptually) without any combinatorial explosion.

    Given a scan of all the pieces and a scan at the same resolution of the finished image, all it takes is "moving" each piece over the finished picture and see if it matches the underlying picture at that spot. To avoid moving on a pixel-by-pixel basis, you can probably "jump" the piece around as most jigsaws seem to have some matrix-like structure of the pieces, so you will not have to check every single pixel-position.

    Of course you will have to check for every orientation (but as most pieces are more or less four-sided, that is only four checks for every useful position).

    The only problem I see is with pieces of a single color (those d****ed "all sky" pieces) as they might fit more than one location. You will have to leave these for the last and try to fit them in given all pieces already in place. Here you might have to try all combinations.

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]
Re^2: Do you suffer "Jigsaw rage"?
by Anonymous Monk on Jan 03, 2005 at 11:32 UTC
    What combinatorial explosion? Unless you have a specially constructed jigsaw puzzle, in a jigsaw puzzle, every side of every piece fits only one other piece (unless the side is on the border). For most jigsaws, determining whether two pieces fit doesn't even require looking at the pictures, just determining wether the pieces lock, and if they do, whether their corners align is enough.

    Considering there's only O(N2) pairs of pieces, with at most 16 ways for two pieces to possibly lock, this leads to a simply quadratic algorithm.

    Of course, that still leads to the problem of determining whether two pieces match, but there's no combinatorial explosion. A combinatorial explosion would happen if you first assemble all (or a fraction of all) the pieces before you determine "match" or "no match".

[reply]

In Section Meditations