How many android patterns are there?

This is a post I've had kicking around in my drafts folder for just over 2 years now so I've decided to publish it as a partly complete problem.

One of my favorite pastimes, when I'm bored, is solving the puzzles on Project Euler¹. I'm not very far through but I've solved 56 at the time of this writing. It's as much about writing the code and learning the language, in my case Python, as it is about actually solving the problems.

The questions are good because they look like there must be a simple way to calculate the answer but it's not immediately obvious². An interesting question that I think is worthy of Project Euler is:

How many possible Android lock screen patterns are there? And how would you calculate it for arbitrarily sized grids?

Let's examine the standard size first, initially if we are just working with a 3 x 3 grid it might help to think of the positions as numbers from 1 to 9.

Initially, we might (incorrectly) think, there are 9 possible starting positions, then 8 remaining moves, then 7 and so on. So it would be 9!

>>> import math
>>> math.factorial(9)
362880

But then we can't use a pattern of fewer than 3 positions so if we remove all there digit options

>>> math.factorial(9) - (9 * 8 * 7)
362376

However this is not right for a few reasons, first 9! (362880) is only the number of combinations of length 9 so to get all the possible combinations

>>> import itertools
>>> positions = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> len(list(itertools.permutations(positions, 9))) # 362880
>>> len(list(itertools.permutations(positions, 8))) # 362880
>>> len(list(itertools.permutations(positions, 7))) # 181440
>>> len(list(itertools.permutations(positions, 6))) # 60480
>>> len(list(itertools.permutations(positions, 5))) # 15120
>>> len(list(itertools.permutations(positions, 4))) # 3024
# Total 985824

Second now we know how many combinations there are, we see that not all combinations are valid, for example while we can have 1234.

We can't have 1324 because there is no way to get from 1 to 3 without going through 2, even if you try to avoid it the line snaps to any positions it passes through.

I found a few incorrect solutions online which simply had a list of invalid moves such as from 1 to 3, from 7 to 9 and so on, but this is not correct either. We can't simply say that moving from 1 to 3 is always invalid because once a position has been used we can jump over it so we can have 2413 as a valid pattern which does go from 1 to 3.

This might be obvious, but just to clearly state it; While you can't jump over an unchecked position, you don't need to move to an adjacent position, for example, knights moves are valid, so we can have 1834

But just when we think we are getting a handle on things, LineageOS (previously CyanogenMod) throws a spanner in the works by allowing grids up to 6 x 6. For a larger grid, I think it's easier to switch to a coordinate system instead of numbered positions.

This brings in a whole new range of moves, for example [(0,3), (5,0), (2,5), (2,4), (2,3), (2,2), (2,1), (2,0), (5,5), (0,2)]

and it brings some new invalid moves, we can't go from [(0,0), (4,2)] without passing through (2,1)

After banging my head on a wall for a while, I searched online for a solution and the best answer I found was a 3 x 3 grid has 389112 possible patterns.

That's great, but every single correct solution I could find involved a brute force approach. Trying every possible combination and then discarding the invalid ones.

When it's just a simple 3 x 3 grid with only 985824 combinations to check brute force is not a bad way to go.

With a 4 x 4 grid (16 positions, over 4,000,000,000,000 combinations to check) brute force becomes incredibly hard but still within the realms of modern computers. By the time we get to 6 x 6 grids (36 positions, more than 2^128 combinations to check) it's downright impossible on current hardware.

There are some things we can do to speed things up though, for example the last two lengths (e.g. on the 3 x 3 grid that combinations of length 8 and 9) will always have the same number of possible combinations because every combination of 8 positions has exactly one corresponding combination of 9 positions.

So the problem that I haven't been able to crack is, can we design an efficient algorithm that can calculate the number of possible moves on an arbitrarily sized grid? not just square grids, what about 3 x 9 for example.

All pictures generated with Lock Pattern Generator

If you are a maths genius and you have a solution please get in touch. I'd love to know and I'll update this post with a link to your solution, michael at hybr dot id dot au