4
$\begingroup$

Early note: This is not homework. I simply regularly create ideas in an attempt to teach myself a language. For what it's worth I'll be using Javascript for this.

That said, I haven't been able to come up with a solution/algorithm outside of brute force. I've searched for various puzzle algorithms but any assumptions regarding puzzle shapes don't fit my simpler criteria so become overly complicated quickly.

I'm calling this a rectangle puzzle rather than a jigsaw puzzle since there is no final picture or restrictions on the overall placement of the pieces.

  • There are only 4 possible piece shapes (row x column) : 1x2, 2x1, 2x2, 4x1
  • These are the only pieces (ie. they may not be rotated or overlap)
  • The play area is 8x4
  • The number of pieces will be undetermined at start
  • Pieces may exist multiple times or not at all
  • The play area does not need to be completely filled
  • The only requirement regarding placement is they must fit in the play area
  • There is no one solution

End solution: What I would like to output is the various arrangements that exist. In other words, given a set of pieces I'd like to know in what ways they may populate the game area. Given the pieces available among other constraints there will be a finite set of solutions.

For the visually minded please see the images.

Play Area

play area

Possible Pieces

possible pieces

Generating a 2D array and fitting the "pieces" via brute force, as said, is possible but I'd prefer to know whether this is already a game of sorts and an algorithm exists. I'm not a math lover so I'm not familiar with any possible solutions that may exist in that space but wouldn't be against investigating if something makes sense.

$\endgroup$
  • $\begingroup$ Is it possible to rotate pieces? The input might be greater than area given? If yes, you want all possible configurations? 2D Packing problem is similar to yours? $\endgroup$ – Evil Feb 23 '16 at 21:25
  • $\begingroup$ The pieces cannot be rotated and, yes, it is possible that not everything will fit. Thanks for the link. $\endgroup$ – McArthey Feb 23 '16 at 21:55
  • $\begingroup$ I know this isn't really an answer, but one of the many screensavers for X (under Unix) tries to fill a rectangular area with polynomioes, and uses brute backtracking starting at an edge. $\endgroup$ – vonbrand Feb 24 '16 at 17:50
  • $\begingroup$ So to be clear: you want all possible solutions, but not brute force. So excluding the mirrored configurations and making search more "pieces" aware is possible, but as far as you want all solutions, this is solution space exhaustion - brute force like. Could you clarify this one? $\endgroup$ – Evil Feb 24 '16 at 20:11
  • $\begingroup$ What i meant by "brute force" was simple exhaustion through iteration of permutations without an algorithm. $\endgroup$ – McArthey Feb 24 '16 at 21:43

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.