Jigsaw Logic: ?s galore

I am working on a 256 piece jigsaw puzzle, but I am having a lot of trouble. Instead of the picture being a landscape or painting, the final image is just a sixteen by sixteen grid of identical question marks. What's worse, the pieces are very interchangeable; any piece which juts out will fit into any piece which juts in. This should make things easier, but really it just enlarges the number of possibilities to check.

There is some regularity to this madness. Each piece is generally square shaped, and each edge of each piece has one of four possible shapes: straight, jutting out, jutting in, or jutting in and out.

This means there are 4 x 4 x 4 x 4 = 256 possibilities for what a piece looks like. I've confirmed that every piece in the box is is different, so each of these 256 possibilities appears once. Unlike a usual jigsaw puzzle, it is OK for there to be straight edges in the interior of the puzzle.

Can you help me put this puzzle together? Is it even possible?

For reference, here is the picture on the front of the box (and a representation of my mental state):

?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?
?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?

• Perhaps the pieces represented by ? s can be shown as a square for a better intuition. Oct 24 '17 at 17:41
• Are the edges going to be straight? Or are they also going to have bumps? Oct 24 '17 at 17:46
• Also, I feel like you could get some weird/interesting answers to this question on Code Golf as well! Oct 24 '17 at 17:54
• @Rob I would be very interested in the name of the real puzzle, please share! Oct 24 '17 at 23:23
• @Mike Earnest Try googling Snowflake Super Square. (I have NO ties to this company.) It's not a perfect match; I don't see that they make a version with two "bumps" per side, but they do use convex and concave in variations, so perhaps the number of combinatorial corresponds? I have purchased other of their acrylic puzzles, and was very pleased. (Oh! I see there is more than one company offering this! Be sure to click around a bit, as the prices are significantly different!)
– user41655
Oct 25 '17 at 0:57

Let's start by just attempting to complete the puzzle, and see how far I get:

WARNING! I didn't know how to effectively spoiler my whole answer, so it's not covered. read at your own risk!

Let's call The possible formations of the sides of a piece 0 for a straight edge, 1 for a single "out", 2 for a single "in", and 3 for the doubled in/out. This naming is arbitrary, but convenient. When I say "side," I'm referring to one of the four borders of a given piece, regardless of its formation.

Consider the puzzle as sixteen rows of pieces. To begin, note that for any top/bottom pairing on a piece, there are 4x4 = 16 possible options for the edges. Also note that there must be an equal number of occurrences (64) of 0's on top and on bottom, of 1's on top as 2's on bottom (and vice versa) and of 3's on top and on bottom. So let's attempt to construct rows such that, in any given row, every top formation is the same and every bottom formation is the same. If we can do this, and start/stop on 0's, then we're done.

First let's make a satisfactory ROW of pieces, without considering the tops and bottoms. Consider the sequence of pairs (0,1),(2,3),(3,1),(2,1),(2,2),(1,1),(2,0),(0,2),(1,3),(3,3),(3,2),(1,2),(1,0),(0,0),(0,3),(3,0) to represent the left and right sides of a line of pieces. This ordered set has each of the 16 possible side pairings appearing exactly once and fits the appropriate rules for connecting pieces. Additionally, this starts and ends on a straight edge, forming the left and right boundaries of rows. So this left/right sequence would go across a whole row regardless of the tops and bottoms.

If we follow the same logic on the tops and bottoms of the rows, going vertically instead of horizontally, we get rows where the top is the same all the way across, and the bottom is the same all the way across. Combine this with the row sequencing above, and you get a grid of non-repeated pieces with straight edges around the top, bottom, left, and right borders of the puzzle.

How can we verify no pieces were re-used and that it contains all 256 pieces?

Being by noting that if the same pattern is used in every row, that any piece in the N-th column will have the same left side as any other piece in that column, and the same right side as every other piece in that column. Note that since all combinations of left/right exist in this column, that left/right pairing does not exist in any other column (as each column has 16 unique pairings). Therefore any piece with that left/right pairing must be in the same column.

Similarly, and piece in the M-th row will have the same top as any other piece in the M-th row, and the same bottom as any other piece in the M-th row, and all pieces with that top/bottom pairing must exist in that row.

Suppose we have two pieces, p1 and p2, at locations in the grid labeled (m1,n1) and (m2,n2), respectively. If the top and bottom sides of p1 match those of p2, then by the above we know that m1 = m2. Similarly, if the left and right sides of p1 match the left and right sides of p2, then n1 = n2. So we have (m1,n1) = (m2,n2), as desired. And if we have 256 pieces without duplication, then we have used all 256 pieces as requested.

So we have a straight-edged border, each piece appearing only once, and all pieces connect correctly to the pieces around them. So we're done!

As for uniqueness of the solution, I can definitively say this is non-unique, because you can "loop" the rows by sliding pieces from the left side to the right until you get to another 0/0 connection, and this can be done independently from a similar slide top-to-bottom of the rows. And there may be alternative formations beyond this method, but at least this method works.

Here's a photo of my solution, using the above 0-1-2-3 notation:

Forgive the horrible formatting, as I haven't figured out how to do much in answers. Anyone is welcome to make it more readable if they feel so compelled.

• OMG, it worked, thanks for your help! I've assembled the puzzle, here is what it looks like: i.stack.imgur.com/G3e0t.png Oct 24 '17 at 23:21
• Your picture of the completed puzzle looks a lot better than mine! Oct 25 '17 at 15:11