A bunch of my coworkers have gotten way into assembling jigsaw puzzles during the workday, so I got this idea it'd be fun to bore them with random facts. I'm trying to think of the odds of assembling a 1000 piece jigsaw puzzle "perfectly," i.e. choosing each piece such that it fits with one of the pieces already in the puzzle.
Assuming that each piece is exactly 1 square inch, that means we probably have a 40x25" puzzle. Using some basic deduction, I can conclude that this leaves 4 "corner" pieces with two possible connections, 122 "edge" pieces with three possible connections, and 874 internal pieces with four possible connections.
From here, I'm sure that the answer has something to do with this: Jigsaw Probability Using that logic, the probability of our first two pieces matching is:
(4/1000) * (2/999) + (122/1000)*(3/999) + (874/1000) * (4/999)
The problem is, I can't figure out how to extrapolate this further, since the next iteration seems like it would depend on which type of piece was chosen. I'm not sure if this is the right approach, because I can envision a scenario where the puzzle is assembled from the center outward, after which every edge piece is guaranteed to fit with probability 1, and I'm not sure how the above sequence could be expanded in a way that accounts for that.
The other approach I thought of was inspired by this: Proof by Induction: Puzzle Pieces Problem
If I could derive the number of possible "perfect" sequences of 999 moves, I could just divide that number by 1000! total possible sequences of selections and that would be the probability. I might be missing something here though, as this line of thinking stands in contrast to this post: Probability of a n-piece puzzle being solved on the first try. Is my reasoning sound? ...which makes the assumption that there's only one possible way to select all pieces that solves it. He also gets into piece orientation which I don't really care about.
Any thoughts are welcome!
I haven't been able to answer this question, but I would like to share some thoughts:
If the growth of the puzzle is reasonably compact, the boundary size $b$ should be roughly proportional to the square root of the number to pieces already placed $p$, so, $b \propto \sqrt{p}$. And the boundary size would be proportional to the number of possible places for the pieces. This should be roughly true as long as there are many pieces left to be placed.
Near the end, almost every leftover piece should have a place, due to small holes or due to edge or percolation effects. So, the probability $Prob$ for a large puzzle with $N$ pieces should depend mostly on the first $n < N$ pieces. $$ Prob \propto \ \prod_{p=1}^{n} \frac{\sqrt{p}}{N-p} . $$
if we assume (based on nothing specific) that $n = N/2$ and approximate the product to its middle term $p = n/2 = N/4$, we get $$ Prob \propto \prod_{p=1}^{N/2} \frac{\sqrt{N/4}}{N-N/4} = \left( \frac{\sqrt{N}/2}{3N/4} \right) ^{N/2} = \left( \frac{2\sqrt{N}}{3N} \right) ^{N/2} = \left( \frac{2}{3} \frac{1}{\sqrt{N}} \right) ^{N/2} , $$ $$ Prob \propto \left( \frac{2}{3} \right) ^{N/2} N^{-N/4} . $$
I have no idea how close can this be to the reality, but it certainly decays fast with N.