Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm just asking myself of how many combinations you would have to go through to solve a jigsaw puzzle by "brute force" if you have $n = (p \times q)$ pieces. To simplify that, I assume that there are no jigsaw pieces with flat edges so that every piece can be at every position.

I've came up with this for the number of combinations $C$: $$C(n) = n! * 4^n$$ $n!$ would be the number of options to arrange the pieces and for each of these options there should be $4^n$ possibilities to rotate them.

Can anyone verify that? Or am I doing a mistake?

Thank you very much in advance

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Yes, that's right.

But it assumes that you can only detect that you have something wrong once you put down the last piece. Usually one can notice that without all pieces placed that the ones that are placed yet don't match up. Doing so leads to a branch-and-bound search which can be quite a bit faster if you're good at detecting wrong branches early.

share|improve this answer
    
Thank you for the quick response. Yes, I'm aware of that limitation but I just wanted to knew how mouch steps it's going to take in the worst case. –  Georgios S. Jan 5 '13 at 11:45
    
One of all these combinations will solve your puzzle, only upside-down :) –  Hendrik Jan Jan 5 '13 at 14:11
    
How do you mean that? –  Georgios S. Jan 5 '13 at 15:20
    
One of your many combinations $C(n)$ is also a solution of the puzzle, but upside down, i.e., rotated 180 degrees. Would that also solve your puzzle? I was (jokingly) suggesting that the worst case scenario would be one step faster. –  Hendrik Jan Jan 6 '13 at 11:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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