[alancalverd (OP)]

The Boss always buys a 1000 piece jigsaw puzzle which we start on Christmas Eve as an alternative to the "seasonal" (i.e. recorded in August)  garbage and re-re-recycled movies on television. Interspersed with plenty of food and wine, it can last until the dreary Celebrity (who?) Best of 2022 and mawkish New Year Countdown fades from the screen. 

At some point towards the end of the business we move from logic (edges and corners, then features with straight lines, then textures....) to picking up a piece at random and looking for a hole it can fit.

Now imagine a machine that can scan the boundaries of all the pieces and translate and rotate their images to fit them together. Let it work at "human speed" - say 1 second to see if B fits to A. Assume the pieces are all white - no picture for reference - and scattered at random.

1.How long would it take to solve the puzzle, based on geometry alone and considering one piece at a time?

2. suppose n pieces are upside down.Let the machine have the capability of flipping any piece over. How long now?

3. what is the effect of introducing one item of prior knowledge: there is no point in fitting another piece to a straight edge?

4. what is the effect of now adding a strategy - look for a corner piece before you start? 

And a joke, in memory of Terry Wogan:

Four rednecks start a-whoopin' and a-hollerin' in a bar. Bar tender says
"Why the noise, boys?"
"We just finished this here jigsaw puzzle"
"Darn took y'all long enough. You guys been workin' it for the last three months."
"Hell yeah, but the label on the box says 'five to eight years' "

Seriously, folks, returning to the random fit machine, given just four shapes, two pieces of string and some glue, how long would it take to evolve a strand of DNA?   

[paul cotter]

A quick spur of the moment guess- factorial 1000 sec. As I said that is just a quick guess, it hurts to think about it in depth, we have an unwelcome viral visitor in our humble abode at the moment though I seem to be least affected. PS I thoroughly agree concerning the thrash that we are exposed to at this time of the year.PPS: I didn't fully read your question- that's my answer to (1), i'm not up for any more.

[Eternal Student]

Hi.

   Similar to @paul cotter ,  I'm not sure I want to consider all of the fine details at the moment.   I think we do want some more information about what sort of algorithm is permitted.

Taking the simplest algorithm for a machine, it will never complete the task.   Without using too many lines to explain, the problem is the straight edges.   The algorithm MUST know that you should stop at a straight edge which is something you allowed only as item no.3 in your post.   Otherwise it may continue by putting another straight edge in contact with that straight edge and that will obviously make it impossible to complete the puzzle.    You could allow an algorithm that includes the ability to rip up some or all of the pieces and start again but then there are going to be more than 1000! possible attempts it could make.   With conventional machine learning techniques, you don't even have to give it an algorithm, just some actions it can take and then just let it go... eventually it will solve the problem.
   I suppose we could also ask about what the ultimate "goal" is supposed to be.  For example, if the machine completes the puzzle so that the picture is upside down or turned at 33.7 degrees that's probably OK.   However, if the pieces are turned face down so that there is no picture visible at all then that probably isn't OK.

Best Wishes.

[alancalverd (OP)]

I'm perfectly happy with an upside down picture, and no problem about "rotation" - I often work from one "side" of the board whilst The Boss always sits at the "bottom".

But I think 1000! is a bit naive as, if you start with one piece A there are four ways that piece B could potentially fit on each side of A. So 16 trials takes 1 second to reject a candidate. But when we have our first "fit",  we have an object AB with six potential attachment points, so it will take a bit longer on average to fit C - we now need 24 trials to reject C. And so forth.
 

[paul cotter]

But you did say "1 second to see if b fits a", and that's where my naïve guess derived from. I just came out of hibernation a short time ago and I think i'll head back- see you all in spring!

[Halc]

A quick spur of the moment guess- factorial 1000 sec.

Let's work from that. The actual answer of course is a statistical thing: At first, hardly any pieces fit to the existing small start, but as the puzzle progresses, the odds of finding a fit increase somewhat in proportion to the exposed area of the blob being built, and inversely proportional to the number of pieces left.

The big answer assumes a human-style poor memory.

Let's assume a completely random process and no two cuts between them alike. The pieces are kept in two bags: Pull and discard.  You start with one piece, a random one.  Then you grab one out of the pull bag and it might fit one of 8 ways on each of the 4 sides, so it takes 32 seconds to reject it into the discard bag, or accept one after over one hour. As the puzzle grows, the 1/250 chance of a piece fitting drops, but it also takes a lot more than 32 seconds to attempt to match your random piece to the growing exposed area of the blob being built, which grows somewhat like a crystal in water.
A human wouldn't try all 32 orientations. I mean, you might have an edge with a button or a hole (my terms for male/female connections) or maybe a wiggle. No point in trying to fit a hole to a hole, so it doesn't really take 32 tries to reject the piece. Where do we draw that line?

I'm sort of in the biz, so given a good memory, all you have to do is scan each piece (999 steps) and put them down (not in a discard bag), remembering where each is. Then you look at one random joint in need of a piece and just reach for the one piece you know that can fit there. The puzzle can be then completed at one piece per second with no randomness at all. There's not even a need to scan the pieces in the memory since they can be sorted by shape and accessed essentially with one lookup operation, an effort that isn't a function of the number of pieces remaining. I actually did this sort of thing for a living, except with 50 million+ piece puzzles which had to be accessed in as few steps as possible. It's how a database works. It gets a little more tricky when the database gets larger than can be held in memory, but you still need to find stuff in it in fewer steps.

Anyway, the scan takes 1000 seconds and then 1000 more to make the puzzle at speed. This assumes inhuman memory. At no point is randomness involved.

[Petrochemicals]

Sounds like a computing thesis project.

[alancalverd (OP)]

I think Halc may have ignored one of the elephants in the room! Consider just one edge of one piece, that looks like a human with  head and shoulders. OK, we characterise it as a "head", but the shoulders of a jigsaw piece can be sloping, hunched, one  of each, square, curved....and the shape is a continuous and random curve, so a database "parallel processing " system memory has to hold the parameters of a truncated arbitrary curve function for each piece, and recognise which part of another such data set produces the complementary curve. The required precision of fit in a real jigsaw is about 0.1 mm at any point on a 3 cm perimeter curve. That's a heck of a lot of data!

My guess is that virtual trial and error would be quicker. I have in mind the overlap of two grey images. You get a fit when there is no black or white visible.

I think a Master's thesis is in there somewhere, and the industrial applications could be very profitable.