4

My 12 year old nephew asked me a hypothetical question that asks if I would be willing to take a bet about puzzling a 1000 piece blank jigzaw puzzle in a month's time. If I succeed I win a large sum of money, if I lose I have to pay the sum. For example 1000000 Icelandic krona (isk).

That got me thinking about how the best way would be to achieve it and if it was realistically possible within a month's time.

The method I propose is a greedy one. You simply take one piece at a time, try it with all the pieces you have successfully put together, if it does not fit you put it in a 'does not fit pile', and then repeat until finished.

If we say that each piece takes 5 seconds + 1 second for each piece in the successfully placed pieces then how long would it take?

Sigmundur
  • 225
  • Are you including pieces not on the perimeter of what you already have? That is, would I need $(5)+(5+1)+...+(5+999)=504000$ seconds, or did I understand the problem wrongly? – Anonymous Pi Mar 17 '17 at 22:11
  • I think it is going to be easier to perform (and a bit easier to estimate the complexity) if you start with the corners and construct the edges first. Then to fill the interior try each potential piece at places with the greatest constraints, i.e. having to fit into the most contact sites. In other words, try each piece at a constrained location until one fits before moving to the next location rather than a piece at every possible location before moving to the next piece. Also, if we are being realistic, sort the pieces by shape type and similarity first. – A. Webb Mar 17 '17 at 22:12

1 Answers1

1

Suppose we find the pieces in reading order $-$ we start in the top left corner, move along that row, then drop a row and continue, and so on for $1000$ iterations.

We might have to try all $1000$ pieces to find the top left corner.

For the next piece there are only $999$ left to try. The worst case scenario is we have to try all of them. So the running total is $1000+999$ tries.

For the next piece there are only $998$ left to try. The worst case scenario is we have to try all of them. S0 the running total is $1000+999+ 998$ tries.

And so on so forth we might have to try $1000+999 + 998 + \ldots + 2 + 1$ times.

Everyone knows the sum of the numbers from $1$ to $1000$ is $500,500$ tries.

$1$ try per $5$ seconds means $720$ tries per hour.

So it could take up to $500500/720 = 695$ hours to brute-force the jigsaw.

A 30-day month is 720 hours long. So you would expect to do the jigsaw in that time. But you are not allowed to sleep or do anything else for that month.

Keep in mind this is an upper estimate. The average time it would take is exactly half the upper estimate: It takes $500$ tries on average to find the first piece and so on. . . So it's 50/50 whether you could brute force the jigsaw with 12 hours work per day.

Daron
  • 10,300
  • Building the edges first saves time - fewer possible pieces to try in each round. Probably not an order of magnitude savings. – Ethan Bolker Mar 17 '17 at 22:27
  • The problem with the naive method is once you have $n$ pieces in place, you have up to $2n+1$ sites to try for each the $(1000-n)$ candidate pieces. Consider an arrangement like $++++$ representing four pieces connected in a straight line, where the protrusions of the $+$ symbols represent possible attachment sites. You have 4 sites along the top, 4 along the bottom and 2 at the ends to try for each potential new piece. So worst case for this step is $(9996-10)10+1$. The next step is worse: $(9995-12)12+1$ because you've created 2 new connection sites. – A. Webb Mar 18 '17 at 01:52
  • @Daron That is kinda exactly what I was thinking at first but then I realized what A. Webb is saying. That is, for every piece you successfully place the complexity of fitting another piece increases. Also, as the pieces left to fit decreases linearly the complexity of fitting another piece increases non-linearly. That is a big part of the problem and I would like to know if someone can take that into account when doing the maths. – Sigmundur Mar 18 '17 at 16:39