Counting Unlock Patterns

In this blog post I will enumerate the number of unlock patterns of the andriod operating system.

Imagine a square array of points, arranged in a three by three formation. We set our selfs the task of tracing a path through a number of these points subjected to the following rules.

1. No point can be visited twice.
2. If a point obstructs an other point, the obstructing point should be visited first.

I will illustrate rule two with an example. Let's say we start our path in the lower left point of our arrangement. Our goal is the upper right point. If we would trace a pattern from our starting point to the target point we visit the center point, which should be included in our path.
Here is an other example which also illustrates rule one. Now our path starts in the center point and again our goal is the upper right point. Instead of directly going to our target we make a little detour via the lower left point. Because we started in the center point, it does not obstruct our goal any more and we can go directly to our goal, the upper right point.

This lengthy explanation is in fact a description of the android unlock pattern. Being a proud owner of a android phone I pondered about the question: "How many unlock patterns are possible". So I set out and wrote a little script to enumerate the different unlock patterns.

The following tables summarizes my findings. The first column list the path lengths. The second column list the corresponding number of unlock patterns. So there is a total of 389498 unlock patterns.

Pattern length	#Patterns
0	1
1	9
2	56
3	320
4	1642
5	7152
6	26016
7	72912
8	140704
9	140704

The most important section of code is displayed here below. It recursively builds a tree of patterns which can be inspected via a visitor. Check out the source if you like.

def generate(self):
for patternElement in self.possible:
nextPossible = self.possible.copy()
nextPossible.remove(patternElement)

if (self.reachable(patternElement)):
child = PatternTree(self,patternElement,nextPossible)
self.children.add(child)
child.generate()