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$

1 Answer 1

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$
4
  • $\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$ Commented Jan 5, 2013 at 11:45
  • $\begingroup$ One of all these combinations will solve your puzzle, only upside-down :) $\endgroup$ Commented Jan 5, 2013 at 14:11
  • $\begingroup$ How do you mean that? $\endgroup$ Commented Jan 5, 2013 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$ Commented Jan 6, 2013 at 11:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .