android lock password combinations

Question

I just came across with this interesting question from my colleague. I'm trying now, but meanwhile I thought I could share it here.

With the password grid shown in the Android home screen, how many valid passwords are possible? min password length: 4 max: 9 (correct me if I'm wrong)

Answer 1

Summary

The full combinations of 4 to 9 distinctive numbers, minus the combinations which include invalid "jump"s.

The Long Version

The rule for Android 3x3 password grid:

• one point for once

• cannot "jump" over a point

The author of the original post used Mathematica to generate all 985824 combinations.

Because there is no "jump", several pairs of consecutive points are invalid.

Delete all invalid combinations to reach the result.

The combinations for 4-to-9-point paths are respectively 1624, 7152, 26016, 72912, 140704, 140704.

The Original Post In Chinese

The reference is from guokr, a site alike Stack Exchange Skeptics in the form of blogs.

Answer 2

I know this question is old, but I answered it in another question (before finding this question) with a brute force approach in python, so adding it here for posterity:

pegs = {
    1: {3:2, 7:4, 9:5},
    2: {8:5},
    3: {1:2, 7:5, 9:6},
    4: {6:5},
    5: {},
    6: {4:5},
    7: {1:4, 3:5, 9:8},
    8: {2:5},
    9: {1:5, 3:6, 7:8}
}

def next_steps(path):
    return (n for n in range(1,10) if (not path or n not in path and 
                                       (n not in pegs[path[-1]] 
                                        or pegs[path[-1]][n] in path)))

def patterns(path, steps, verbose=False):
    if steps == 0:
        if verbose: print(path)
        return 1
    return sum(patterns(path+[n], steps-1) for n in next_steps(path))

So you can list all the # of patterns for any number of steps:

>>> [(steps, patterns([], steps)) for steps in range(1,10)]
[(1, 9),
 (2, 56),
 (3, 320),
 (4, 1624),
 (5, 7152),
 (6, 26016),
 (7, 72912),
 (8, 140704),
 (9, 140704)]
>>> sum(patterns([], steps) for steps in range(4,10))
389112

This is not the most efficient way of solving it because you could use reflections and only calculate a 4*corner + 4*mid-edge + 1*middle, e.g.:

>>> patterns([], 6) == 4*patterns([1], 5) + 4*patterns([2], 5) + patterns([5], 5)
True