Screen Pattern Lock

Level: L3-L5 Topics: Backtracking, Recursion, Combinatorics, Graph Traversal

Problem Statement

Consider an R x C grid of dots (like a phone unlock screen). A pattern is a sequence of distinct dots connected by straight lines. Count the total number of distinct patterns of any length (1 to R*C dots) that can be drawn on the grid.

Basic rules:

• Each dot can be visited at most once per pattern.
• Connections are only allowed between horizontally or vertically adjacent dots (no diagonals).
• A pattern can start at any dot.

Background & Constraints

• R and C are small (typically 2 to 4), since the total number of patterns grows very fast.
• A single dot counts as a valid pattern of length 1.
• Two patterns are distinct if their sequences of dots differ (order matters).
• The grid is indexed by (row, col) starting from (0,0).

Examples

2 x 2 grid:

(0,0) — (0,1)
  |        |
(1,0) — (1,1)

Patterns of length 1: 4 (each dot alone) Patterns of length 2: 8 (each of the 4 edges, in both directions) Patterns of length 3: 8 (e.g., (0,0)→(0,1)→(1,1), and all rotations/reflections) Patterns of length 4: 8 (Hamiltonian paths — visit all 4 dots)

Total: 28 patterns

Hints & Common Pitfalls

• Use backtracking: from each starting dot, recursively try all valid next moves, marking dots as visited.
• At each step, count the current partial pattern as valid (patterns of any length count).
• For small grids, brute-force backtracking is perfectly efficient.
• Exploit symmetry to speed up computation: on a square grid, corners are equivalent, edges are equivalent, and the center (if it exists) is unique. Multiply counts accordingly.
• A common mistake is only counting full-length patterns (Hamiltonian paths) instead of all prefixes.

Follow-Up Questions

1. Allow diagonal connections: Now dots can also connect diagonally (8-directional adjacency). How does the count change? The implementation change is minimal — just expand the neighbor list.
2. Minimum length requirement: Patterns must use at least 4 dots. Why is this important in practice? (Security: short patterns are too easy to guess.) How does this affect your counting logic?
3. Allow connecting any two dots (hardest): Any unvisited dot can be the next in the sequence, regardless of distance. However, if a straight line between two dots passes through an intermediate dot, that intermediate dot must already be visited. This mirrors the actual Android unlock pattern rules. How does checking the "pass-through" constraint change your backtracking?