A tangle is a length of string which has been twisted around itself (possibly forming one or more knots) and then had its two ends joined. If the tangle can be converted into a simple loop without cutting the string, it is an unknot; otherwise, it is a knot.
Knots may be represented by two-dimensional projections called knot diagrams, with letters labeling crossings, places where one portion of the string passes over or under another. Sections of string between two crossings are called arcs. The section of string passing under another is indicated by a broken line in the diagram. (See Figure 1 on the accompanying handout or an online figure of a knot diagram [without crossing labels].)
Kurt Reidemeister (1948) showed that any unknot can be untangled by performing an appropriate series of only three types of moves, called Reidemeister moves. Type I consists of removing a twist from an arc. Type II involves passing two arcs, one of which lies above the other, across each other. Type III requires passing an arc that lies above or below the crossing formed by two others past that crossing. (See Figure 2 on the handout or an online figure illustrating the Reidemeister moves.)
For example, the tangle of Figure 1 may be shown to be an unknot by the series of Reidemeister moves given in Figure 3. We indicate a Type I move by "Twist(x)" and a Type II move as "Poke(y, z)", where x, y, and z are crossing labels. Note that only Type I and Type II moves are required for this particular example; your assignment is likewise limited to these two types.
Randall Weiss (1987) suggested a representation for knot diagrams which he dubbed a tripcode: an ordered list of pairs
( crossing-name, crossing-type )which indicates the order in which crossings are visited during a continuous circuit of the diagram. A crossing-name is a simple identifier, such as "a", corresponding to a crossing label; the crossing-type is either "o" (for "over") or "u" (for "under"). For example, a tripcode for the knot diagram in Figure 1 is:
(a, o), (b, u), (c, u), (d, o), (d, u), (a, u), (b, o), (e, u), (f, o), (g, o), (h, u), (f, u), (g, u), (h, o), (e, o), (c, o)
Note that tripcodes should be considered to be circular lists, as the starting point is arbitrary, and the last crossing in the list is adjacent to the first.
The presence of a Reidemeister Type I move ("twist") in a knot diagram corresponds to an adjacent pair of crossings with identical crossing-names in the tripcode. Removal of a twist in the tangle is represented by removal of the corresponding pair from the tripcode. For example, the first twist removed in Figure 3 was at crossing "d", which is indicated in the tripcode by
. . . (d, o), (d, u) . . .
The move is performed by deleting these pairs from the tripcode.
A Reidemeister Type II move ("poke") corresponds to finding two crossing-names with like crossing-types in adjacent pairs twice in the tripcode. The move is performed by removing all four entries from the tripcode. For example, the overlapped arcs are represented in the sample tripcode by
. . . (f, o), (g, o) . . . (f, u), (g, u) . . .
Note that the following tripcode configuration would also indicate that a "slide" was possible:
. . . (f, o), (g, o) . . . (g, u), (f, u) . . .
Write a set of Prolog predicates which, given a tripcode representation of a knot diagram as input, performs Reidemeister moves of Types I and II, printing a list of moves performed, followed by a message that the tangle is an unknot if the resulting tripcode is empty, or by the value of the resulting tripcode if it is not empty. The program should then terminate with "no".
We will modify the form of the tripcode in order to conform to the format of a Prolog list, rather than a LISP-like list, i.e., a comma-separated list in brackets. For example, the tripcode for the knot diagram shown in Figure 1 of the handout for Assignment 2 would be:
[[a,o], [b,u], [c,u], [d,o], [d,u], [a,u], [b,o], [e,u],
[f,o], [g,o], [h,u], [f,u], [g,u], [h,o], [e,o], [c,o]]
Your program must be invoked by
?- tangle([[a,o],[b,u],...]).
For example, the following query should produce output similar to that shown below:
?- tangle([[a,o],[b,u],[c,u],[d,o],[d,u],[a,u],[b,o],[e,u],
[f,o],[g,o],[h,u],[f,u],[g,u],[h,o],[e,o],[c,o]].
Twist(d)
Poke(f,g)
Twist(h)
Twist(e)
Poke(a,c)
Twist(b)
The tangle is an unknot.
no
The order in which operations are performed may differ; for example, the sequence shown in Figure 3 is also possible.
Figure 4 illustrates a tangle which is a knot. The corresponding query might produce the following output:
?- tangle([[a,o],[b,o,],[c,o,],[d,u,],[e,o,],[f,o,],[b,u,],[g,o,],[d,o,],[e,u],
[h,o,],[i,o,],[j,o,],[h,u,],[i,u,],[j,u,],[f,u,],[c,u,],[g,u,],[a,u]]].
Poke(h,i)
Twist(j)
Poke(e,f)
Twist(a)
[[b,o,],[c,o,],[d,u,],[b,u,],[g,o,],[d,o,],[c,u,],[g,u]]
no
(This tangle could be shown to be a knot after performance of a Type III move.)
Note that performance of one move may create another. Also, remember that the first and last crossings in a tripcode are adjacent.
Please hand in a hardcopy listing of your solution to this assignment (to ensure that the formatting which you carefully prepared is preserved) and submit the source code for your solution using one of the following forms.
EITHER by file upload:
OR by cutting and pasting text:
Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account (if you have one).
The desired characteristics of your solution are the same as for the previous assignments: correctness, design and efficiency, style and documentation, knowledge of the language. Note, however, that Prolog is an inherently inefficient language; your solution should be efficient only in the sense that clauses can be placed in an appropriate order to minimize backtracking. You may use cuts for efficiency, but they are not necessary. (Cuts may be used to prevent your program from searching for alternate orders in which to untie a tangle, however, i.e., to terminate after the first solution has been found.)
Points will be awarded according to the following weighting:
| Correctness | 60% | |
| Correctness of validity checking | 10% | |
| Correct handling of twist | 10% | |
| Correct handling of overlap | 10% | |
| Correct handling of wraparound | 10% | |
| Recognition of unknot | 5% | |
| Recognition of knot | 10% | |
| Display of resulting knot | 5% | |
| Design and efficiency | 20% | |
| Style and documentation | 20% | |
(Not required, no extra credit, but interesting.)
Type III moves are also detectable from the tripcode. Your program could find and perform such moves under user control. Note that Type III moves
An Introduction to Knot Theory -- Web site with definitions, illustrations, and thought experiments
Knot Theory -- Web site from a geometry course at York University
Reidemeister Moves -- an entry from
Eric Weisstein's Encyclopedia of Mathematics
illustrating the Reidemeister moves, which are here called
"Twist" (Type I), "Poke" (Type II), and "Slide" (Type III)
Meredith, M. "An Effective Lisp Project for a Programming Languages Course," in SIGCSE Bulletin, vol. 22, no. 4 (Dec. 1990), p. 45.
Peterson, I. The Mathematical Tourist. New York: W.H. Freeman, 1988.
Reidemeister, K. Knotentheorie. New York: Chelsea, 1948.
Weiss, R. Detecting ribbon knots. Unpublished thesis, University of Illinois at Chicago, 1987.