# Solve a jigsaw puzzle

A jigsaw puzzle consists of (usually rectangular-ish) pieces. On each side of a piece, there is either an edge or a connector (a term I made up). A connector is either a tab sticking out (outie) or a slot facing inwards (innie). Two pieces can be joined if the outie tab can fit into the innie slot. The goal is to assemble all the pieces into a single unit.

To turn it into a computational problem, we'll assume that the jigsaw puzzle is a perfect rectangular grid of pieces, and instead of having innies and outies, we'll use corresponding positive integers, which I'll call "connector IDs". In other words, two pieces can put next to each other if they have the same number on their adjacent side.

## The challenge

As input, take in a series of lines of 5 positive integers. The first number indicates the ID of the piece; the next four represent the nature of the pieces' top, right, bottom, and left sides respectively. One symbol of your choice should be reserved to represent an edge.

• The piece IDs will always start at 0 or 1 (your choice) and increase by 1 for each successive line; in other words, the piece ID is equal to the line number. If you want, you can omit the piece ID from the input format (so there are only 4 integers per line).
• You can assume the set of connector IDs will either be $$\\{0,1,\ldots,m-1\}\$$ or $$\\{1,2,\ldots,m\}\$$ for some positive integer $$\m\$$ -- your choice.

Output, in some reasonable format, a grid of piece IDs such that every adjacent piece in a column/row has the same number on their neighboring side and all the side corresponding to edges are on the edge of the grid. There is no rotation allowed. (If there are multiple solutions, you can output any valid solution.)

## Example

In this illustration, I will represent each piece as the following:

/.1.\
0 0 2
\.3./


Where the number in the center is the piece ID and the numbers on the edges are the identifiers for the type of edge/connector. In this example, I'll use 0 to indicate an edge side.

Suppose we had the 3 by 3 jigsaw puzzle

/.0.\ /.0.\ /.0.\
0 1 2 2 7 3 3 4 0
\.3./ \.1./ \.5./
/.3.\ /.1.\ /.5.\
0 2 1 1 8 6 6 5 0
\.4./ \.4./ \.5./
/.4.\ /.4.\ /.5.\
0 3 2 2 9 3 3 6 0
\.0./ \.0./ \.0./


(Note that the same connector ID can appear on multiple neighboring sides.) This could be represented as the input

1 0 2 3 0
2 3 1 4 0
3 4 2 0 0
4 0 0 5 3
5 5 0 5 6
6 5 0 0 3
7 0 3 1 2
8 1 6 4 1
9 4 3 0 2


We would then expect an output like

1 7 4
2 8 5
3 9 6


Standard loopholes are forbidden. Since this is , the shortest program wins.

• This seems like a good challenge -- it needs more test cases, though. Also, if the number of pieces was prime, eg, would that imply the solution had to be a single row of pieces? Commented Sep 9, 2022 at 13:59
• I believe the possible sets of connector IDs should be $\{0,1,…,m−1\}$ or $\{1,2,…,m\}$. Commented Sep 9, 2022 at 14:13
• Unfortunately except in the special case of symmetric connectors, the connection relationship is antireflexive and antitranstivive, so you can't actually use the same digit for both sides of a connector.
– Neil
Commented Sep 9, 2022 at 16:29
• Obligatory Garfield.
– Neil
Commented Sep 10, 2022 at 7:01
• Can one assume that the puzzle has always at least one solution? Commented Sep 12, 2022 at 14:27

# Python3, 210 bytes:

def f(m,c=[]):
if(C:=len(c))==9:yield[c[i:i+3]for i in range(0,9,3)];return
for i in{*m}-{*c}:
t=[]
if C%3>0:t+=[m[c[-1]][1]==m[i][3]]
if C>3:t+=[m[c[C-3]][2]==m[i][0]]
if all(t):yield from f(m,c+[i])


Try it online!

• I think it is only the example that is three by three and that in general, we must find a working arrangement of any possible height & width. Commented Sep 9, 2022 at 17:26
• 156 bytes Commented Sep 9, 2022 at 18:10

# Python3, 866 bytes:

y=[[int(i)for i in l.split()]for l in x.split('\n')]
u=[]
w=lambda z:[p for p in y if p[1:3]==z and not any(p in s for s in u)]
k=False
o=True
d=lambda z,g:z.append(g)
d(u,w([0,0]))
def v(x,t):
for i in range(len(x[0])):
e=x[0][i]
if len(x)==1:
d(u,t+[e])
if c():return o
u.pop()
else:
if v(x[1:],t+[e]): return o
return k
def c():
a=u[-1];b=[]
if len(a)==1 and a[0][3:]==[0,0]:return o
if a[0][4]!=0:
d(b,w([0,a[0][4]]))
if b[-1]==[]:return k
for i in range(1,len(a)):
d(b,w([a[i-1][3],a[i][4]]))
if b[-1]==[]:return k
if a[-1][3] != 0:
d(b,w([a[-1][3],0]))
if b[-1]==[]:return k
return v(b,[])
c();m=0;f=[]
for r in u:
if m<len(r):[d(f[i],r[i][0])for i in range(m)];d(f,[r[-1][0]]);m+=1
else:[d(f[i+(m-len(r))],r[i][0])for i in range(len(r))]
for g in f:g.reverse()
print('\n'.join([' '.join([str(i)for i in g])for g in f]))


Try It Online

here(tio) is simple program to construct test cases

• Welcome to Code Golf, and nice answer! Commented Oct 17, 2022 at 18:36