1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – George Jan 5 '13 at 11:45
  • $\begingroup$ One of all these combinations will solve your puzzle, only upside-down :) $\endgroup$ – Hendrik Jan Jan 5 '13 at 14:11
  • $\begingroup$ How do you mean that? $\endgroup$ – George Jan 5 '13 at 15:20
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jan 6 '13 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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