Log in

No account? Create an account
Artur Bergman [entries|archive|friends|userinfo]
Artur Bergman

[ website | O'Reilly Radar ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Jun. 28th, 2007|12:55 am]
Artur Bergman
Can you solve a jigsaw puzzle in linear time?

What does your gut tell you? If you think about it, does this change? If you think you can, why do you think so. If you think it is impossible, please tell.

[User Picture]From: jtrevino
2007-06-28 09:33 am (UTC)
I can solve all two piece jigsaw puzzles in linear time. Furthermore, I can solve all three piece jigsaw puzzles in linear time. So by the principle of mathematical induction I can indeed solve all jigsaw puzzles in linear time. I can't speak for others.
(Reply) (Thread)
[User Picture]From: matthew
2007-06-28 04:34 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: 2shortplanks
2007-06-28 09:37 am (UTC)
My gut tells me no, because I don't have perfect memory. I have to pick up a piece and then look at one of it's edges and scan each and every other piece to see if it fits.

This isn't how we solve jigsaw puzzles in reality however. We sort them so we can more easily find the corresponding piece.

Now can a computer solve a jigsaw in linear time? Maybe. If my computer can compute a hash value for each edge (and for argument's sake say that it's the same value for both edges that match) then it can, assuming a really good hash alogrythm, approximate linear time. For each piece it can look at each edge and either connect it to a previously stored edge or store it in a hash table of future edges to connect.

Or have I made a mistake here?
(Reply) (Thread)
[User Picture]From: jered
2007-06-28 11:43 am (UTC)
Does the puzzle have uniquely matching edge pairs?
(Reply) (Thread)
[User Picture]From: crucially
2007-06-28 09:06 pm (UTC)
That is the question i think. If yes, then you can, if not, then you can't.
(Reply) (Parent) (Thread)