The problem: How many valid reconfigurations, as defined below, are there for a given puzzle?

For example, does this problem--or an equivalent problem; or perhaps a more limited variation, say $1 \times n$; or with non-square rectangular pieces to limit the number of external edge matches--have a conventional name?

Did I actually come up with something new, or am I just describing a known problem with my own terminology because I don't know any better?

The definitions as formally as I can, based on simple physical jigsaw puzzles with unique squiggly parts and uniform straight parts:

• puzzle: an $m \times n$ grid full of identically-sized, identically-oriented pieces
• piece: a square of $4$ edges; denoted $a_{i,j}$ for the piece in row $i$, column $j$ of puzzle $A$ where $1 \leq i \leq m$ and $1 \leq j \leq n$
• edge: a means of joining two pieces; is either internal or external
• joined: two pieces sharing exactly one edge (either in the puzzle or a reconfiguration)
• internal edge: a unique edge joining two pieces in the puzzle; denoted $\overline{a_{i,j}a_{g,h}}$ for joined pieces $a_{i,j}$ and $a_{g,h}$
• the external edge: each of the identical $2m + 2n$ edges in the puzzle that are not internal
• a reconfiguration: the puzzle, modified by operating on individual pieces by means of right-angle rotations and piece-size translations, such that the end result is contiguous, i.e., any given piece is related to any other piece via a series of edges
• a valid reconfiguration: a reconfiguration wherein no two pieces are vertically or horizontally adjacent unless the edge they share is either the internal edge they share from the puzzle, or the external edge (i.e. an internal edge matches only as it does in the puzzle, and cannot match a different internal edge, nor the external edge)

Informal clarifications

Note that, necessarily, a valid reconfiguration is made by various joins of the external edge that were not part of the puzzle, and it will not be a neat rectangle in the end.

That is to say, you can glue the straight parts together on the inside, you can't mismatch the squiggly parts, and some squiggly parts will now be on the outside.

I actually thought of this question when considering such an arrangement of a normal physical puzzle for an artistic idea (maybe Picasso's cubism collides or colludes with Warhol?) so it is entirely made with real, physical puzzles in mind.

Why this seems like a tricky combinatorial problem to me

For $1 \times 1$, the puzzle cannot be reconfigured because no joins are possible because there is only one piece.

For $1 \times 2$, there are $9$ valid reconfigurations, namely those made from the various combinations of matching any of the $3$ straight edges of $a_{1,1}$ with any of $3$ straight edges of $a_{1,2}$ (here pictured as A and B, respectively, because re-doing work in Excel wore me out):

For $1 \times 3$, I count:

• $\overline{a_{1,1}a_{1,2}}$ intact, with one of $a_{1,3}$'s straight edges joined to one of $a_{1,2}$'s $= 3*2 = 6$
• $\overline{a_{1,1}a_{1,2}}$ intact, with one of $a_{1,3}$'s straight edges joined to one of $a_{1,1}$'s $= 3*3 = 9$
• $\overline{a_{1,2}a_{1,3}}$ intact, symmetrical with $a_{1,1}$ as in the above two cases $= 6 + 9 = 15$
• $a_{1,1}$ joined to $a_{1,2}$ via a straight edge, and $a_{1,3}$ joined to $a_{1,2}$ via $a_{1,2}$'s other straight edge $= 3*2*3 = 18$
• $a_{1,1}$ joined to $a_{1,3}$ via a straight edge, and $a_{1,2}$ joined to $a_{1,3}$ via another of $a_{1,3}$'s straight edges $= 3*3*2*2 = 36$
• $a_{1,1}$ joined to $a_{1,3}$ via a straight edge, and $a_{1,2}$ joined to $a_{1,1}$ via another of $a_{1,1}$'s straight edges $= 3*3*2*2 = 36$

...for a total of $120$ valid reconfigurations, if I didn't miss anything.

For a $2 \times 2$, it certainly gets hairier:

• $\overline{a_{1,1}a_{1,2}}$ and $\overline{a_{1,1}a_{2,1}}$ intact, with $a_{2,2}$ removed and rejoined elsewhere $= 3*6 = 18$
• symmetry of above with each of the other pieces functioning as $a_{2,2} = 3 * 18$
• $\overline{a_{1,1}a_{1,2}}$ intact, and $a_{2,2}$ joined to $a_{1,2}$ by a straight edge:
• includes the case where the other joins are $\overline{a_{2,1}a_{2,2}}$, $a_{1,1}$'s top external edge with $a_{2,1}$'s bottom external edge, and $a_{1,2}$'s top external edge with $a_{2,2}$'s bottom external edge
• not as simple to calculate by straight multiplication, though: naturally cannot include invalid reconfigurations like where the other joins are $a_{1,1}$'s top external edge with $a_{2,1}$'s bottom external edge and $a_{2,2}$ rotated once clockwise so that its right edge joins $a_{1,2}$'s top edge, because $a_{2,2}$'s bottom edge, which is external, cannot join $a_{2,1}$'s right edge, which is the internal edge $\overline{a_{2,1}a_{2,2}}$...here it's already tricky
• ...
• total unknown

For $1 \times 4$, there would, I would think, be more solutions than $2 \times 2$, since there are 10 external edges instead of 8, but it would also be tricky to calculate because of combinations of external edge joins that would need non-matching internal edges to join, which they can't.

Holes for slightly larger puzzles

Holes may arise in valid reconfigurations:

The example above shows three different puzzles and a valid reconfiguration for each one that happens to have a hole. (Straight edges are solid, and internal edges are dotted, even though different dotted edges may only join if they're joined in the original. In a real puzzle these are the unique squiggly cuts resulting in two pieces sharing a pair squiggly parts that can only fit each other.) The top $3 \times 4$ puzzle's reconfiguration has a hole with all internal edges, the middle $2 \times 4$ puzzle's reconfiguration has a hole with a mix of internal edges and straight edges, and the bottom $1 \times 8$ puzzle's reconfiguration has a hole with all straight edges. All of these are valid reconfigurations.

Bounds

A completely brute force approach to counting these may be taken by looking at all possible reconfigurations, then excluding the invalid ones (any where the graph is disconnected, or unmatching internal edges are adjacent.) Then the question of rotational equivalence could be addressed, AFAICT simply by dividing by 4.

The biggest area to check is $mn$ by $mn$, and each square in it can be occupied by one of the $mn$ original pieces in one of 4 rotations, or left blank. One cannot use a simple permutation function for the upper bound here because of the rotations--once a piece is used in a particular rotation, the possibility of using its other three rotations in the same potential reconfiguration goes away.

Sequences

On the topic of just the $1 \times n$ set of cases, we have the sequence 0, 9, 120, ... (or, if you want to include the original configuration, 1, 10, 121, ... but it's not clear if it is, in fact, related to any known sequence. Perhaps some software could be written to calculate a few more numbers in the sequence to help with this.

• I'm not sure that I understand the objects you are formalizing entirely, but they sound a lot like "stretchy polyominoes". ( en.wikipedia.org/wiki/Polyomino ) If that's the case, I can't see how the top edge of C could attach to the left edge of A without causing some sort of localized hole between the top edge of A and the top edge of B. – Eric Stucky Dec 26 '13 at 20:20
• @EricStucky, I might've mis-formalized it. I was going for the most basic of jigsaw puzzles, so "stretchy" strikes me as probably not what I meant. If you're talking about the 2-by-2 case, they can't attach: the top edge of C is a unique internal edge, whereas the left edge of A is the straight edge. I'll edit to try to clarify this. – Kev Dec 27 '13 at 14:43
• Although you may be able to apply polyomino-based theorems to this problem due to their equivalence to jigsaw puzzles: dl.acm.org/citation.cfm?id=1275561 – Kev Dec 27 '13 at 15:13
• I'm sorry, I was talking about the $1\times 3$ case. I have a hard time visualizing how, say, the right end of C attaches to the left end of A could be joined in the plane if the pieces are not stretchy. Correct me on this, but I think that in the $2\times 2$ case you can't do anything with the top edge of C because it is internal. But I do not see how it is unique; surely the right edge of C is also internal? – Eric Stucky Dec 27 '13 at 22:05
• @EricStucky re: 1-by-3, it's because B and C do not have to join. Hopefully that helps with your 2-by-2 question. I'd better clarify that in the original. – Kev Dec 29 '13 at 2:20