Blind man's jigsaw puzzle

[mathmagician]

A blind old man loves jigsaw puzzles. He starts them by picking a piece at random and putting it down. He then picks another piece at random and tries to attach it to each side of the piece he started with (trying all four rotations and flipping it over) and repeats until the piece fits. Then he picks another piece at random and tries to attach it to the part of the puzzle he already has. He continues doing this until the puzzle is solved. What is the expected number of pieces he will try in order to solve an m by n puzzle?

[phaze]

He will try m X n pieces as that is the number of pieces in the puzzle. Some pieces he will probably need to try more than once for other parts of the puzzle but that was not the question now was it?

[mathmagician]

He will try m X n pieces as that is the number of pieces in the puzzle. Some pieces he will probably need to try more than once for other parts of the puzzle but that was not the question now was it?

Technically, you're right. What i mean to ask though is how many times will he pick up a piece.

Note: When a piece does not fit, he puts it back into the pile and may pick it up again immediately. If so, it still counts as picking up another piece.

The solution I found is recursive. I have closed forms for m=1 and m=2. I'm still working on generalizing it.

[phil1882]

the chances of success are determined by the perimeter. with 1 piece, you have a perimeter of 4. with 8 pieces, you could potentially have many different perimeters; ranging from 1 long perimeter of 18, or a more stout one of 12. so i don't really see any good way to analyze the problem other than running a bunch of simulations. even this may not be very helpful.

Edited February 9, 2013 by phil1882

[Prime]

The solution would be straightforward, but...

From OP, each jigsaw puzzle piece can connect to four other pieces.

After picking the first bit at random, there may be 4 pieces out of mn - 1 that connect to it. With replacement, the average number of picks before getting one of those is (mn - 1)/4. Whereafter there are 6 exposed sides yielding the average of (mn - 2)/6.
Thus we get the series: (mn-1)/4 + (mn-2)/6 + (mn-3)/8 + ... + 1 for the average number of piece picking.
We could work with this series and try finding a closed-form expression for it.

However, not all pieces are equal. There are edge pieces, which connect to others only on 3 sides. (2m+2n-8 of those.) And there are 4 corner pieces, which connect with only 2 others.
So if the blind man happened to pick a corner piece first at the probability of 4/(mn), then the first term of the series would be (mn-1)/2. Also, the number of available sides would be increased by 1 instead of 2, when connecting an edge piece to the middle pieces build up.

To help us solving this problem, the blind man must first put aside all the edge and corner pieces by feeling straight edges with his fingers. Then he should start working on all the middle pieces.

[Prime]

Actually, it's more complicated. Like Phil1882 noted.

Fitting another piece may increase or decrease the existing perimeter by anything from +2 to -4.

[superprismatic]

A matrix showing the expected number of draws necessary to complete an

n by m (n,m<11) blind jigsaw using 1,000,000 iterations for each (n,m):

001.00 002.00 003.67 006.00 009.00 012.66 017.01 022.00 027.67 033.99
002.00 004.50 008.00 012.51 018.00 024.49 031.99 040.54 050.02 060.50
003.67 008.00 013.66 020.66 028.93 038.54 049.46 061.72 075.33 090.19
006.00 012.51 020.66 030.39 041.78 054.76 069.38 085.62 103.53 123.08
009.00 018.00 028.93 041.78 056.49 073.14 091.75 112.26 134.75 159.05
012.66 024.49 038.54 054.76 073.14 093.72 116.62 141.59 168.83 198.33
017.01 031.99 049.46 069.38 091.75 116.62 143.85 173.69 206.02 240.83
022.00 040.54 061.72 085.62 112.26 141.59 173.69 208.56 246.02 286.52
027.67 050.02 075.33 103.53 134.75 168.83 206.02 246.02 289.33 335.68
033.99 060.50 090.19 123.08 159.05 198.33 240.83 286.52 335.68 388.04

[mathmagician]

Below are closed-form expressions for 1xn and 2xn cases

For 1xn, expected number of pieces is (n^2+2)/3

For 2xn, expected number of pieces is (n^2+2n+1)/2

I don't believe there is a polynomial for 3xn because I found the exact values for 3x3 and 3x4 and their denominators are huge. I could be wrong though.