Android unlock patterns

A phone lock screen has nine dots in a 3 x 3 grid, numbered 1 to 9 row by row. A pattern is a sequence of distinct dots. You may move from one dot straight to another unless the line between them passes through a dot that is not yet in the pattern. Count the valid patterns that use between 4 and 9 dots.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_patterns(min_len: int, max_len: int) -> int — the number of valid patterns of min_len to max_len dots, inclusive.
• A jump passes through a dot in eight cases: along a row or column (1–3 through 2, 4–6 through 5, 7–9 through 8, 1–7 through 4, 2–8 through 5, 3–9 through 6) and along the diagonals (1–9 and 3–7 through 5). That move is allowed only once the middle dot is used. Moves such as 1–6 or 1–8 pass through no dot.

Example

count_patterns(1, 1)  ->  9
count_patterns(2, 2)  ->  56       # 72 ordered pairs minus the 16 blocked jumps
count_patterns(4, 4)  ->  1624
count_patterns(4, 9)  ->  389112

Constraints

• 1 <= min_len <= max_len <= 9; each dot is used at most once.

Clarifying questions

• Is a move like 1 to 6, which passes between dots, always allowed?
• May a pattern pass over a dot it has already used?
• Do two patterns with the same dots in a different order count separately?

What a strong answer covers

• A skip[a][b] table of the middle dot for each blocked jump, and depth-first search with a visited set that counts every prefix whose length is in range.
• Symmetry: the four corners give the same count, as do the four edge dots, so count from 1, 2 and 5 and compute 4·corner + 4·edge + centre.
• The search space is at most 9! orders, so brute force with backtracking is fine; a bitmask of used dots keeps it fast.
• Checks: length 1 gives 9 and length 2 gives 56.

Follow-ups

• Memoize on (current dot, used mask) and explain the saving.
• Generalize to an n x n grid, where a jump can pass through several dots (use the gcd of the step).
• Return the patterns themselves, or the k-th one in order.