Mathcounts 1999 National Competition Sprint Problem 4

A fly starts at one vertex of a cube with edge length 1 inch and randomly walks along edges of the cube. What is the number of inches in the longest distance that it could walk without retracing any edge?

cube.lp:

%   5--6
%  /  /|
% 1--2 7
% |  |/
% 3--4

e(1,2;5;3).
e(2,1;4;6).
e(3,1;4;8).
e(4,3;2;7).
e(5,1;6;8).
e(6,5;2;7).
e(7,4;6;8).
e(8,3;5;7).

#const nedges = 12.

longestpath.lp:

% Find a longest path in an undirected graph, where length = number of edges in path.

% e(X,Y) - There is an undirected edge from X to Y.
% edge(X,Y) - e(X,Y) plus e(Y,X).
% path(N,X,Y) - step N of the path takes the edge (X,Y).

edge(Y,X) :- e(X,Y).
edge(X,Y) :- e(X,Y).

% Any edge could be the first.
1 { path(1,X,Y) : edge(X,Y) } 1.

% Subsequent edges must start at the ending vertex of the previous edge.
0 { path(N+1,Y,Z) : edge(Y,Z) } 1 :- path(N, X,Y), edge(X,Y), N=1..nedges.

% A path must not repeat a previous edge.
:- path(N,Y,Z), path(M,Y,Z), N < M.
:- path(N,Y,Z), path(M,Z,Y), N < M.

#maximize [ path(N,X,Y) : N = 1..nedges : edge(X,Y) ].

#hide.
#show path/3.
#show length/1.

display:

#!/usr/bin/perl -w
use strict;
my @path;
while (<>) {
  if (/path/) {
    @path = ();
    while (/path[(](\d+),(\d+),(\d+)[)]/g) {
      $path[$1-1] = "($2,$3)";
    }
  }
}
print "@path [length=", scalar(@path), "]\n";

Running it:

$ clingo cube.lp longestpath.lp | perl display
(1,2) (2,6) (6,5) (5,1) (1,3) (3,4) (4,7) (7,8) (8,5) [length=9]