# Android's Locking Pattern

For the rest of this discussion, I will use the following convention to designate a locking pattern:

0 | 1 | 2 |

3 | 4 | 5 |

6 | 7 | 8 |

- It needs to contain at least four dots (and obviously, no more than nine).
- Once a dot is lit, it can't be used again.
- You can use one or several "knight moves", such as in [0 5 4 2]:

In this example, the knight move is between 0 and 5. - You cannot go over an unlit dot without lighting it. For example, the pattern [0 2 1 4] is illegal, because moving your finger between 0 and 2 will light 1.
- Once a dot is lit, you can use it to reach another unlit dot. For example, both [0 4 3 5] and [0 4 5 3] are legal:

This example is a bit ambiguous but you get the idea: I trace [0 4 5] and then I slide over 4 again to reach 3.

With these constraints in place, I wondered how many combinations were actually possible, so I wrote a short program to simulate it. It turns out there are quite a few: 389,112. Here is a breakdown:

4 dots: 1624 solutions

5 dots: 7152 solutions

6 dots: 26016 solutions

7 dots: 72912 solutions

8 dots: 140704 solutions

9 dots: 140704 solutions

Total: 389112

If you're not convinced, here is a full list of all the four dot patterns (the page uses a big canvas object, it might take a few seconds to load).

Still, I'm not sure my calculations are right, so I'd like you, dear reader, to confirm my numbers, and optionally explain how you coded your solution...

{{ nComments() }}