Continuing my re-discovery of Logo, I thought I’d try to implement a backtracking solution to finding a Hamiltonian cycle in a graph. Backtracking is easily implemented by treating the routine as a boolean function, which simply returns the truth value of the existence of a Hamiltonian cycle. The basic schema works like this, given a graph and a path :

**isHamilton**(,):

- If contains all vertices of G without repeats, and the end of P is the same as the start, then return TRUE.
- For all vertices adjacent to the end of and which are not contained in output the result of
**isHamilton**(, ). - return FALSE

For a nice introduction to backtracking, see https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html.

We will enter our graphs as *adjacency lists*: this is a list of lists, where each member list consists of a vertex followed by all its adjacent vertices. For example, the adjacency list of the wheel graph on 6 vertices, with 1 as the central vertex and vertices 2 – 6 in clockwork order:

would look like this:

`[[1 2 3 4 5 6] [2 1 3 6] [3 1 2 4] [4 1 3 5] [5 1 4 6] [6 1 2 5]]`

We start with two helper programs, one which tests the adjacency of two vertices, and one which tests whether a vertex can be added to an existing path:

to adjacentp :vert1 :vert2 :graph output memberp :vert1 bf item :vert2 :graph end to allowable :vert :path :graph make "bool1 memberp :vert :path make "bool2 adjacentp :vert (last :path) :graph output (and (not :bool1) :bool2) end

The Hamiltonian code now simply copies the above algorithm description:

to hamilton :path :graph print :path make "count :count + 1 if equalp (count :path) (count :graph) ~ [ifelse adjacentp (first :path) (last :path) :graph [output "TRUE] [output "FALSE]] foreach firsts :graph ~ [if allowable # :path :graph ~ [if hamilton lput # :path :graph [output "TRUE]]] output "FALSE end

The `print :path` statement does exactly that; the idea is that when the program finishes its run with a positive result, the last path printed before output TRUE will be the cycle we want. Here’s an example:

? make "wheel6 [[1 2 3 4 5 6] [2 1 3 6] [3 1 2 4] [4 1 3 5] [5 1 4 6] [6 1 2 5]] ? show hamilton [1] :wheel6 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 TRUE

As an example of a non-Hamiltonian graph, consider this simple graph on 5 vertices:

? show hamilton [1] [[1 2 4 5] [2 1 3] [3 2 4 5] [4 1 3] [5 1 3]] 1 1 2 1 2 3 1 2 3 4 1 2 3 5 1 4 1 4 3 1 4 3 2 1 4 3 5 1 5 1 5 3 1 5 3 2 1 5 3 4 FALSE

Note how in this last example, the routine explored all possible paths before giving up and returning FALSE. This is a very inefficient program; there are ways to speed up such a program, some of which are listed in the references here. When I ran this program on the Barnette-Bosák-Lederberg graph, it took several hours, and 4,173,760 calls of the program before it returned FALSE.

Clearly there are many possible improvements which could be made: for example there should be a “calling” program for which you simply enter a graph, and then the above program is used as a driver. Also, printing out all paths as they are formed is unnecessary (although it provides insight into the backtracking approach). The `allowable` program returns FALSE immediately if the path is empty: this is why in its current form the `hamilton` program needs a non-empty path at the start. We could also more conventionally enter a graph as a list of edges (for an unordered graph, each edge would be an unordered list of two elements – being the vertices at its ends), and construct an adjacency list from that. But I was only interested in a proof of concept, and in how relatively easy it was to use Logo for it.