7
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ This sounds like a great question! +$1$ $\endgroup$ – Clayton Mar 9 at 2:37
  • 1
    $\begingroup$ this question is much more interesting than the 3 quoted questions. :) you're looking at the number of ways to "grow" the grid starting with any cell and adding one adjacent cell at a time. if you consider the grid as a graph then this reminds me of depth-first search, bread-first search, Dijkstra etc in how you add one adjacent node at a time. but i dont know of any result about the number of distinct ways to visit every node. $\endgroup$ – antkam Mar 9 at 17:02
  • $\begingroup$ Thinking of it as a graph is a really interesting approach! An approach like that might be able to more readily yield the number of "perfect" traversals that visit each node exactly once... I'll think of this for a bit and update the question if I come up with anything useful. $\endgroup$ – stuart Mar 10 at 3:26
  • $\begingroup$ apparently there is some math called "percolation theory" related to this, modeling e.g. infection spreading on a graph incl. on a grid. but the setting usually assume parallel infection, not sequential. and they dont seem to be asking an enumeration question like yours. $\endgroup$ – antkam Mar 11 at 16:50
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.