SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

How long does it take to solve a jigsaw?

January 5th, 2017, 10:26 am

I don't mean finding some optimal strategy, I mean how long should it take a normal person using standard techniques such as doing edges first?

Assume NxN to start with, and roughly square pieces (so no clues about orientation). Can discuss extreme cases (at one extreme pieces numbered, at the other extreme all pieces the same colour). Also discuss easy bits, such as writing (as long as there's not too much of it), and difficult bits, etc. etc. 

Bring in randomness, so looking at expected time as a function of N. Can have different parameters representing ease/difficulty of different types/areas of picture. So each jigsaw might have a difficulty rating besides just N.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 1:54 pm

A few questions about sources of variation:

1. Is the solver given free access to the box top showing the final picture? One common solver strategy is to estimate the (x,y) coordinates of pieces based matching the colors & patterns in the piece to the final picture.

2. How much table top space does the solver have? The smaller the table top, the longer the solution process because the solver can't have all the loose pieces unstacked or have room for partial subassemblies. I would guess that solver time declines asymptotically in table area, getting to within a few percent of the minimum as that table size expands to about 3 or 4X the area of the final puzzle.

3. Is there an average level of physical deftness in terms of how long it takes a "normal person" to physically select, pickup, move, and place one peice? Should time estimates be expressed in terms of "puzzle operations" with each person having an intrinsic POPS (Puzzle Operations Per Second) rating?

P.S. I assume N is the total number of pieces so that the puzzle is sqrt(N)xsqrt(N).
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 2:19 pm

A few rough estimates:

1. Simple brute force on the edges (comprised of O(sqrt(N)) pieces: pick an edge piece, compare it to every other of the O(sqrt(N)) pieces. O(N)

2. Simple brute force on the middle: pick a piece, compare it to every other of the N pieces. This takes O(N^2) puzzle operations.

3. Piece clustering: Assume there are O(sqrt(N)) clusters of pieces based on color/texture with brute force solution of each cluster: O(N*sqrt(N)) puzzle operations.
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 2:28 pm

A few questions about sources of variation:

1. Is the solver given free access to the box top showing the final picture? One common solver strategy is to estimate the (x,y) coordinates of pieces based matching the colors & patterns in the piece to the final picture.

2. How much table top space does the solver have? The smaller the table top, the longer the solution process because the solver can't have all the loose pieces unstacked or have room for partial subassemblies. I would guess that solver time declines asymptotically in table area, getting to within a few percent of the minimum as that table size expands to about 3 or 4X the area of the final puzzle.

3. Is there an average level of physical deftness in terms of how long it takes a "normal person" to physically select, pickup, move, and place one peice? Should time estimates be expressed in terms of "puzzle operations" with each person having an intrinsic POPS (Puzzle Operations Per Second) rating?

P.S. I assume N is the total number of pieces so that the puzzle is sqrt(N)xsqrt(N).
1. Yes. Standard jigsaw conditions.

2. Good question. Maybe start with infinite? Floors are usually big enough.

3. I was thinking of proportional to some function of N. So deftness doesn't matter. Unless some operations are different from others for different people. It might breakdown to observation time and positioning time.

Ok, have N as total number of pieces.
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 3:14 pm

The edge strategy is a subset of "find the M<=N pieces with a certain property." E.g. Bright red pieces (Santa's coat), Hairy bits (Santa's beard), writing (Santa's list of good boys and girls),...

Then we have to find and configure the M_i pieces with property i from the N-M_1-M_2-...-M_{I-1} remaining. Finishing with the set of pieces with nothing in common(!)

And then what order to do the various properties, small or large M_i first?
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 3:33 pm

No, it'll be faster than that implies. Just once through all N to divide into piles with the same property.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 4:35 pm

Good point about "edge" defining one of the clusters of pieces of a certain property. Yet physical (and visual) edge pieces do have a special characteristic that makes them different from other clusters of pieces. Edges have only a 1-D permutation of arrangements whereas clusters reside in 2-D. Linear chains of pieces seem much easier to layout than the general 2-D tiling case.

One major issue with human puzzle solvers is the role of memory during the puzzle solving process and the interplay between very slow external physical matching/arrangement operations versus very fast internal cognitive matching/arrangement operations. Generally speaking, time complexity analysis ignores the efficiency of execution of operations in heterogeneous algorithms running on heterogeneous architectures. Yet the actual clock time is incredibly sensitive to these efficiency issues. I would estimate that cognitive matching/arrangement (looking at a piece and seeing in the mind's eye where it goes) might be 1,000 to 100,000 times faster than physical pairwise pick-n-try operations. The intrinsic parallelism of pattern matching a visual piece within a larger visual memory would make it quite fast. But this memory-hosted process takes time to establish as the solver learns the puzzle and sorts through a lot of the pieces.

I'd think that the rate of piece placement (snaps-per-minute?) follows a lumpy fourth-order curve: slow (in the familiarization phase), accelerating to fast (during the small-cluster construction phase), reverting to slow (getting to the difficult bits), slowly rising to somewhat fast (increasingly obvious last-possible-place choices).

Overall, I'm still thinking the process is O(N*sqrt(N)) for puzzles in the hundreds or thousands of pieces. If one considers extremely large puzzles with millions or billions of pieces, one would need to multiply by another O(sqrt(N)) to reflect the scaling of the amount of physical movement in sorting and placing the pieces (e.g., a billion piece puzzle would be on the order of 1/2 to 1 km on a side).
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 4:42 pm

No, it'll be faster than that implies. Just once through all N to divide into piles with the same property.
Hmmm... Doesn't this depend on the distribution of the sizes of the M_i clusters? In the example of a 1000-piece Christmas puzzle, there might be 30 clusters (writing, beard, santa's hat, elf faces, reindeer horns, etc.). Some of the clusters will be trivial (e.g., the 5 pieces with Santa's beard) but some will be beastly hard (e.g., the 100 pieces of sky or 100 pieces of scattered patches of snow). The hard clusters will dominate the time requirements.
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 4:48 pm

I have a famously bad memory (except for musicals of the '40s and '50s). So I am always surprised when I remember having previously seen a piece and realising where it goes!

Also I lose interest if/when I hit an unproductive patch.
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 4:54 pm

When I sort socks (eg a box with 300 socks) I toss them into piles based on features. I might have 10 piles: red socks, kid socks etc (non-disjoint, the feature that sets it apart from 90% of the other socks, each sock can be classified in many ways, this is a information theoretical argument). Then I repeat it for each pile until I get high pairing rates. Once I've processed all piles I redistribute the leftovers into a couple of piles based of new features. I also use my memory in this step. All in all it takes me only a couple of hours.
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 5:00 pm

? 300 pairs !

A lot of family members? A lot of inbreeding (more than the usual number of feet per person)? Chinese laundry? Not washing frequently?
 
User avatar
Paul
Topic Author
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 5:06 pm

Optimally satisfying jigsaw:

Edges take O(N).

Suppose K characteristics, including no characteristics, evenly distributed. Each group then takes O(N^2/K^2). So make that O(N), i.e. K=O(N^1/2). Makes each group, inc edges, equally satisfying. Then time taken is

O(N^3/2)
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 5:22 pm

When I sort socks (eg a box with 300 socks) I toss them into piles based on features. I might have 10 piles: red socks, kid socks etc (non-disjoint, the feature that sets it apart from 90% of the other socks, each sock can be classified in many ways, this is a information theoretical argument). Then I repeat it for each pile until I get high pairing rates. Once I've processed all piles I redistribute the leftovers into a couple of piles based of new features. I also use my memory in this step. All in all it takes me only a couple of hours.
This can be solved much faster with a leaf-blower air cannon and a couple of lasers:

1. Feed the socks one at a time into the air cannon pointed up at a 45 degree angle -- the socks will sort in down-range distance according to a metric linked to mass and surface area.

2. A high-power blue laser on the left side of the muzzle will nudge all non-blue socks toward the right.

3. A high-power red laser on the left side of the muzzle will nudge all non-red socks toward the left.
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 5:26 pm

I don't like sorting them and it's easier to buy new ones instead. I'm not allowed to throw them all out and do a new start so we have linear growth.

You need to better specify the "actions" you do. E.g. finding a "mostly red" tile, how much time does that take? That depends on what primitive action you allow for:
a) you look through a straw, examining one tile at a time -> full scan, O(N^2)
b) you immediately spot it: O(1)

The method I use with my piles is called a https://en.wikipedia.org/wiki/Bloom_filter by examining a couple of features: is it red Y/N with prob1, is it small Y/N with prob2 I can find the correct pile on O(K) time. Assuming that all answers have a 50-50 Y/N rate this means that the probability of finding a match in a pile is O(N^2 / 2^K). setting K to log2(N^2) seems optimal?

..but that's for socks! I'll ponder about jigsaw!
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

Re: How long does it take to solve a jigsaw?

January 5th, 2017, 5:27 pm

When I sort socks (eg a box with 300 socks) I toss them into piles based on features. I might have 10 piles: red socks, kid socks etc (non-disjoint, the feature that sets it apart from  90% of the other socks, each sock can be classified in many ways, this is a information theoretical argument). Then I repeat it for each pile until I get high pairing rates. Once I've processed all piles I redistribute the leftovers into a couple of piles based of new features. I also use my memory in this step. All in all it takes me only a couple of hours.
This can be solved much faster with a leaf-blower air cannon and a couple of lasers:

1.  Feed the socks one at a time into the air cannon pointed up at a 45 degree angle -- the socks will sort in down-range distance according to a metric linked to mass and surface area.

2. A high-power blue laser on the left side of the muzzle will nudge all non-blue socks toward the right.

3. A high-power red laser on the left side of the muzzle will nudge all non-red socks toward the left.
I'm actually thinking about making an app for it. My phone will point me towards matches on the screen.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On