How Many Possible Unlock Paths?

I was recently at dinner with some Linux kernel hackers who were showing off their smartphones. These phones have an interesting unlock mechanism: the phone displays an 3-by-3 array of circles, and the user traces out a path among the circles. If the path is correct, the phone unlocks.

The paths are not arbitrary. From what I could see, here are the rules governing them:

  1. Paths are composed of a series of straight line segments.
  2. Each line segment connects a pair of circles.
  3. If the preceding line segment arrived at a given circle, then the next line segment must leave that same circle.
  4. A given circle may be visited only once.
  5. A line segment may pass over a given circle without visiting it only if that circle has already been visited. (Attempting to pass over a not-yet-visited circle will instead visit that circle.)

How many unique paths are there?

Let's first try for some upper bounds. There are 28 different possible line segments, and a given path must travel through some subset of those line segments. There are 2^28 possible subsets of line segments, for 268,435,456 paths. Except that direction matters, so we double that for a total of 536,870,912 paths, which is about half a billion.

But this is a gross overestimate, as it includes a very large number of disconnected line segments, as well as a large number of paths that are not possible to trace without visiting a circle twice.

Another possible upper bound is 9!, because there are nine circles, and the best you can do is to visit all nine of them in some order. This upper bound might be too large because there are some orders that are not possible, for example, you cannot start with a segment going from any of the corners to the opposite corner without passing through the circle in the center. On the other hand, this upper bound might be too small because it ignores paths that visit fewer than nine circles. The latter could be accounted for by a sum of terms consisting of binomials times factorials, but given that we are only talking about millions of possibilities, it is time to write some code and let the computer do the counting.

This program claims that there are 389,497 possible paths. But are you willing to take this program's word for it?

Update

An anonymous commenter noted that there is also a minimum sequence length of four. The program above has been updated to take this minimum into account, resulting in 389,112 paths.