Solve a jigsaw puzzle

Question

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 code-golf, the shortest program wins.

Answer 1

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!

Answer 2

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