7
$\begingroup$

Let's say we have a jigsaw puzzle with N pieces. Each piece has 4 sides and can only have one of three fits: a straight fit, a concave fit and convex fit. A side can only fit with another side if both sides are a straight fit or if they are opposites, i.e. one side is concave and the other is convex. Also, the sides on the perimeter can only be straight. How can I determine, without actually putting it together, if it indeed has a solution or not?

$\endgroup$
  • $\begingroup$ It's not Game Theory. You wold have much more success if you asked someone working in Graph Theory. $\endgroup$ – ClassicEndingMusic Jun 7 '17 at 6:09
  • $\begingroup$ @ClassicEndingMusic sorry, I've updated it $\endgroup$ – mr nooby noob Jun 7 '17 at 6:33
  • 1
    $\begingroup$ At this moment the only thing that I know that can prove that it is NOT solvable if the number of concave and convex sides are not the same. For example, a 2x2 puzzle where the top two and bottom left pieces are all perfect squares (all four sides are straight) but the last piece has three sides that are straight and one that isnt. In this example there would be 7 straight sides and one side thats either conaved or convex. $\endgroup$ – mr nooby noob Jun 7 '17 at 7:59
  • 1
    $\begingroup$ Also, the opposite does not prove anything, ie if the number of concave = the number of convex, does NOT prove anything. Take the above example, except now, have the last piece consist of two concave sides and two convex. Those sides will not fit the any other piece's sides, since the other 3 pieces only consist of straight pieces. $\endgroup$ – mr nooby noob Jun 7 '17 at 8:03
  • 2
    $\begingroup$ Played with this for awhile today: The problem is in NP. A 1-row/ column variant is trivial. All promising algorithms for a 2-dimensional variant look extremely hard/slow... One ambiguity, do you allow rotation and reflection of pieces? just rotation? or are you given the correct orientation by default? $\endgroup$ – Artimis Fowl Jun 8 '17 at 4:45

Your Answer

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

Browse other questions tagged or ask your own question.