[Math] Android lock screen (9 dots) has exactly 140240 possible ways to (un)lock it

This is simple graph theory. We just enumerate all paths over nodes/vertices, using networkx Python library.

And there are 140240 paths. Way too many to enumerate manually, of course.

#!/usr/bin/env python3
# you may need to run: pip3 install networkx
import networkx as nx
G = nx.Graph()

"""
1 2 3
4 5 6
7 8 9

lines like these are also counted:
* . .
. . *
. * .
"""

# start vertex and a list of neighbour vertices
edges={1: [2, 4, 5, 6, 8],
2: [1, 3, 4, 5, 6, 7, 9],
3: [2, 5, 6, 4, 8],
4: [1, 2, 5, 7, 8, 3, 9],
5: [1, 2, 3, 4, 6, 7, 8, 9],
6: [2, 3, 5, 8, 9, 1, 7],
7: [4, 5, 8, 2, 6],
8: [4, 5, 6, 7, 9, 1, 3],
9: [5, 6, 8, 4, 2]}

for x in range(1, 9+1):
    for y in edges[x]:
        G.add_edge(x, y)

for start in range(1, 9+1):
    for stop in range(1, 9+1):
        if start==stop:
            continue
        for x in nx.all_simple_paths(G, start, stop):
            print (x)

[1, 2]
[1, 4, 2]
[1, 4, 5, 2]
[1, 4, 5, 3, 2]
[1, 4, 5, 3, 6, 2]
[1, 4, 5, 3, 6, 8, 7, 2]
[1, 4, 5, 3, 6, 8, 9, 2]
[1, 4, 5, 3, 6, 9, 8, 7, 2]
[1, 4, 5, 3, 6, 9, 2]
[1, 4, 5, 3, 6, 7, 8, 9, 2]

...

[9, 2, 7, 6, 1, 4, 5, 8]
[9, 2, 7, 6, 1, 4, 8]
[9, 2, 7, 6, 1, 4, 3, 5, 8]
[9, 2, 7, 6, 1, 4, 3, 8]
[9, 2, 7, 6, 1, 5, 3, 4, 8]
[9, 2, 7, 6, 1, 5, 3, 8]
[9, 2, 7, 6, 1, 5, 4, 8]
[9, 2, 7, 6, 1, 5, 4, 3, 8]
[9, 2, 7, 6, 1, 5, 8]
[9, 2, 7, 6, 1, 8]

Full list.

Thanks to @mztropics who once pointed to a bug.

At reddit.

(the post first published at 20220416.)

List of my other blog posts.

Subscribe to my news feed

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.