I have been doing a jigsaw puzzle. It's a picture of a nebula in deep space taken by the Hubble space telescope. About a quarter of the pieces are either pitch black or very dark grey. I have had to set up a lighting rig and use magnifiers to help determine if pieces are in the right place. I have also been trying to speed up my progress by using information theory and statistics.
To find a piece that fits as quickly as possible you need to reduce the set of contenders as much as you can. Ordinarily you'd look for something "roughly the right colour" but that didn't help me at all. To start with I divided the pieces into 4 hash buckets: 1 head; 2 heads on an axis; 2 heads on adjacent sides; 3 heads. Interestingly there were no pieces with 0 or 4 heads. I soon noticed that the pieces were wider than they were tall and I divided the hash buckets even further: 1 head on a vertical axis; 1 head on a horizontal axis; 2 heads on the vertical; 2 heads on the horizontal; 2 adjacent heads on an L bend; 2 adjacent heads on a J bend; 3 heads vertical; 3 heads horizontal. In some cases this narrowed down the set of pieces which might fit to a few dozen or a mere handful.
I also noticed that the cleave lines generally alternated whether the heads went left or right (up/down for horizontal cleave lines) and nowhere on the part of the puzzle I had completed were there more than 2 adjacent heads in the same direction. This meant that in could make much better guesses about what shaped piece I was looking for and in some places I knew for sure what all 4 sides would look like even though I only had 2 to work from.
I'm always disappointed and cross when a database says "fuck it, I'll just compare every single combination of rows and see which ones match (it would probably phrase it as -> Nested Loop (cost=388.64..105744.98 rows=6645 width=13) (actual time=0.341..27.475 rows=5000 loops=4) ) but in many places in my jigsaw I did resign myself to trying every single piece that was left to see what would fit.
Richard "Cinderella" B
No comments:
Post a Comment