Python 3, 457 316 306 bytes
E=enumerate
V={'+'}
Q=[[(-j,i,k)for i,u in E(open(0))for j,v in E(u)for k in[{v}&V,'join'][u[j:j+2]=='|-']]]
while Q:
a,b,c,d,*e=A=tuple(x//2for y,x in sorted((y,x)for x,y in E(Q.pop())));e or exit('NOT')
if{A}-V:V|={A};Q+=[[c,d,a,b]+e,A,A[2:]+A[:2]][a<c<b<d:][c<a<d<b:]
if b==d:Q=[[a,c]+e]
exit('KNOT')
Huh?
The program first converts the knot to a rectangular diagram, which has the following restrictions:
- No two vertical or horizontal segments lie on the same line.
- No vertical segment crosses over a horizontal segment.
For example, the first test case is converted to the following rectangular diagram:
+-----------+
| |
| | +-------+
| | | |
| +-------+ | | |
| | | | | |
| | +---+ | |
| | | | | |
| | | +---+ |
| | | |
| | | +-------+
| | | | | |
+-----+ | | | |
| | | | | |
| +---+ | | |
| | | | | |
| | +-------------+ | |
| | | | | |
| | | +---+ |
| | | | | |
| | | | +---+
| | | |
+-+ | |
| |
+-+
which we uniquely represent by the sequence of y coordinates of the vertical segments, from right to left:
(5,10, 1,9, 8,10, 9,12, 5,12, 1,4, 0,3, 2,4, 3,7, 6,8, 7,11, 2,11, 0,6)
It then searches for simplifications of the rectangular diagram as described in Ivan Dynnikov, “Arc-presentations of links. Monotonic simplification”, 2004. Dynnikov proved that from any rectangular diagram of the unknot, there is a sequence of simplifying moves that ends at the trivial diagram. Briefly, the allowed moves include:
- Cyclically permuting the vertical (or horizontal) segments;
- Swapping consecutive vertical (or horizontal) segments under certain configuration constraints.
- Replacing three adjacent vertices that lie in the very corner of the diagram with one vertex.
See the paper for pictures. This is not an obvious theorem; it does not hold if, say, Reidemeister moves that do not increase the number of crossings are used instead. But for the particular kinds of simplifications above, it turns out to be true.
(We simplify the implementation by only permuting vertical segments, but also allowing the entire knot to be transposed to interchange horizontal with vertical.)
Demo
$ python3 knot.py <<EOF
+-------+ +-------+
| | | |
| +---|----+ +-------+
| | | | | |
+-------|------------|---+
| | | |
+---+ +---+
EOF
KNOT
$ python3 knot.py <<EOF
+----------+
| |
| +--------------+
| | | |
| | +-|----+ |
| | | | | |
| +-----+ | |
| | | |
| +------|---+
| |
+---------------+
EOF
NOT
$ python3 knot.py <<EOF # the Culprit
+-----+
| |
+-----------+ |
| | | |
| +-+ | +---|-+
| | | | | | | |
| +-|-------+ | |
| | | | | | | |
+-|-+ | | +---+ |
| | | |
+---|---------+
| |
+-+
EOF
NOT
$ python3 knot.py <<EOF # Ochiai unknot
+-----+
| |
+-|---------+
| | | |
| | +-+ | |
| | | | | |
+-|-|---|-|-+ |
| | | | | | | |
| | | +---|---+
| | | | | |
+-------+ | |
| | | |
| +-------+
| |
+-------+
EOF
NOT
$ python3 knot.py <<EOF # Ochiai unknot plus trefoil
+-----+ +-----+
| | | |
+-|---------+ |
| | | | | |
| | +-+ | +---+ |
| | | | | | | |
+-|-|---|-|-+ +---+
| | | | | | | |
| | | +---|-----+
| | | | | |
+-------+ | |
| | | |
| +-------+
| |
+-------+
EOF
KNOT
$ python3 knot.py <<EOF # Thistlethwaite unknot
+---------+
| |
+---+ +---------+
| | | | | |
| +-------+ | |
| | | | | |
| | | +---+ |
| | | | | |
| | +-------+ |
| | | | | |
| +-------+ | |
| | | | | |
+-----------+ | | | |
| | | | | |
| +-----------+ | | |
| | | | | |
| | +-------------+ |
| | | |
| | +-----+
| | | |
| | +---+
| | | |
+---------------------+ |
| |
+---------------------+
EOF
NOT
$ python3 knot.py <<EOF # (−3,5,7)-pretzel knot
+-------------+
| |
+-|-----+ |
| | | |
+-|-+ +-------+ |
| | | | | |
+-|-+ +---+ +---+
| | | | | |
| | +---+ +---+
| | | | | |
| | +---+ +---+
| | | | | |
| +---+ +---+
| | | |
| | +---+
| | | |
| | +---+
| | | |
| +---+
| |
+-----+
EOF
KNOT
$ python3 knot.py <<EOF # Gordian unknot
+-------------+ +-------------+
| | | |
| +---------+ | | +---------+ |
| | | | | | | |
| | +-------------+ +-------------+ | |
| | | | | | | | | | | |
| | | +---------+ | | +---------+ | | |
| | | | | | | | | | | | | | | |
| +-------+ | +-------+ +-------+ | +-------+ |
| | | | | | | | | | | | | | | |
+-------+ | +-------+ | | +-------+ | +-------+
| | | | | | | | | | | | | | | |
| +-------+ | | | | | | | | +-------+ |
| | | | | | | | | | | | | | | |
+-------+ | | | | | | | | | | +-------+
| | | | | | | | | | | | | | | |
| +-----+ | | | | | | +-----+ |
| | | | | | | | | | | |
+---------+ | | | | +---------+
| | | | | | | |
+---------+ | | +---------+
| | | | | | | |
| | +-----------------+ | |
| | | | | |
| +---------------------+ |
| | | |
+-----------+ +-----------+
EOF
NOT
2Can we assume it's a knot (possibly the unknot) or can it be a link of >1 connected components? – msh210 – 2016-05-03T07:03:36.313
@msh210 Yes, you can assume it's a single knot :-) – r3mainer – 2016-05-03T20:50:31.170
36+1 Great question. Tempted to put a bounty on this one to encourage folks to jump into that knot theory. – Digital Trauma – 2014-06-06T16:50:45.533