Android unlock patterns

Count valid Android unlock pattern sequences with hidden adjacency rules between non-adjacent dots.

graphs dfs backtracking counting

On a 3x3 Android lock screen, the dots are numbered 1 to 9 in a row-major order:

1 2 3
4 5 6
7 8 9

A pattern is a sequence of distinct dots (no repeats). A sequence is valid if for every consecutive pair of dots (a, b), if the line segment between a and b passes through an intermediate dot c that has not yet been visited, then the move is invalid. If c has already been visited, the move is allowed.

Write a function `count_android_patterns(length)` that takes an integer `length` (1 <= length <= 9) and returns the total number of valid patterns of exactly that length. The same sequence in reverse is considered a different pattern if the length > 1 (e.g., 1-2 and 2-1 are distinct).

Implement the function in Python. The function should use backtracking or DFS to count patterns.

Constraints

- `length` is an integer between 1 and 9 inclusive.
- The function should return an integer.
- The grid is fixed as 3x3 with dots numbered 1-9 as shown.
- Intermediate dot rule: the line between a and b passes through c if c is the midpoint (collinear) and lies directly between them on the grid. The only such pairs are: (1,3), (3,1), (1,7), (7,1), (1,9), (9,1), (3,7), (7,3), (3,9), (9,3), (7,9), (9,7), (2,8), (8,2), (4,6), (6,4).
- Note: (1,9) and (3,7) pass through 5; (2,8) passes through 5; (4,6) passes through 5.
- The algorithm should not use recursion depth issues for length <= 9 (max depth 9).

Example

```python
>>> count_android_patterns(1)
9
>>> count_android_patterns(2)
56
>>> count_android_patterns(3)
320
```

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Define a mapping of pairs that skip an unvisited middle dot.

Use DFS from each starting dot, tracking visited dots and current pattern length.

When moving from dot a to dot b, if the middle dot m exists in the skip map and m is not visited, the move is invalid.

For efficiency, precompute the skip map and use recursion or an explicit stack.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.