Android Unlock Patterns

medium backtracking bitmask

Problem

Count the number of unlock patterns of length between m and n on a 3×3 grid of keys, with the rule that connecting two keys passes through any intermediate key that hasn't been used.

Inputm = 1, n = 2

Output65

Length 1: 9 patterns. Length 2: 56 patterns.

def number_of_patterns(m, n):
    skip = [[0]*10 for _ in range(10)]
    skip[1][3] = skip[3][1] = 2
    skip[1][7] = skip[7][1] = 4
    skip[3][9] = skip[9][3] = 6
    skip[7][9] = skip[9][7] = 8
    skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5
    visited = [False]*10
    def dfs(cur, remaining):
        if remaining < 0: return 0
        if remaining == 0: return 1
        visited[cur] = True
        total = 0
        for nxt in range(1, 10):
            if visited[nxt]: continue
            if skip[cur][nxt] == 0 or visited[skip[cur][nxt]]:
                total += dfs(nxt, remaining - 1)
        visited[cur] = False
        return total
    res = 0
    for l in range(m, n + 1):
        res += dfs(1, l - 1) * 4  # corners
        res += dfs(2, l - 1) * 4  # edges
        res += dfs(5, l - 1)
    return res

function numberOfPatterns(m, n) {
  const skip = Array.from({length: 10}, () => new Array(10).fill(0));
  skip[1][3] = skip[3][1] = 2;
  skip[1][7] = skip[7][1] = 4;
  skip[3][9] = skip[9][3] = 6;
  skip[7][9] = skip[9][7] = 8;
  skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
  const visited = new Array(10).fill(false);
  function dfs(cur, remaining) {
    if (remaining < 0) return 0;
    if (remaining === 0) return 1;
    visited[cur] = true;
    let total = 0;
    for (let nxt = 1; nxt <= 9; nxt++) {
      if (visited[nxt]) continue;
      if (skip[cur][nxt] === 0 || visited[skip[cur][nxt]]) total += dfs(nxt, remaining - 1);
    }
    visited[cur] = false;
    return total;
  }
  let res = 0;
  for (let l = m; l <= n; l++) res += dfs(1, l - 1) * 4 + dfs(2, l - 1) * 4 + dfs(5, l - 1);
  return res;
}

class Solution {
    int[][] skip = new int[10][10];
    boolean[] visited = new boolean[10];
    public int numberOfPatterns(int m, int n) {
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] =
        skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        int res = 0;
        for (int l = m; l <= n; l++) res += dfs(1, l - 1) * 4 + dfs(2, l - 1) * 4 + dfs(5, l - 1);
        return res;
    }
    int dfs(int cur, int rem) {
        if (rem < 0) return 0;
        if (rem == 0) return 1;
        visited[cur] = true;
        int total = 0;
        for (int nxt = 1; nxt <= 9; nxt++) {
            if (visited[nxt]) continue;
            if (skip[cur][nxt] == 0 || visited[skip[cur][nxt]]) total += dfs(nxt, rem - 1);
        }
        visited[cur] = false;
        return total;
    }
}

class Solution {
    int skip[10][10] = {0};
    bool visited[10] = {false};
    int dfs(int cur, int rem) {
        if (rem < 0) return 0;
        if (rem == 0) return 1;
        visited[cur] = true;
        int total = 0;
        for (int nxt = 1; nxt <= 9; nxt++) {
            if (visited[nxt]) continue;
            if (skip[cur][nxt] == 0 || visited[skip[cur][nxt]]) total += dfs(nxt, rem - 1);
        }
        visited[cur] = false;
        return total;
    }
public:
    int numberOfPatterns(int m, int n) {
        skip[1][3]=skip[3][1]=2; skip[1][7]=skip[7][1]=4; skip[3][9]=skip[9][3]=6; skip[7][9]=skip[9][7]=8;
        skip[1][9]=skip[9][1]=skip[2][8]=skip[8][2]=skip[3][7]=skip[7][3]=skip[4][6]=skip[6][4]=5;
        int res = 0;
        for (int l = m; l <= n; l++) res += dfs(1, l - 1) * 4 + dfs(2, l - 1) * 4 + dfs(5, l - 1);
        return res;
    }
};

Explanation

We count valid patterns by depth-first search, trying to extend the line one key at a time. The only tricky rule is that some moves jump over a middle key, which is only allowed if that middle key was already used.

The skip table encodes those middle keys: for example, going from key 1 to key 3 passes over key 2, so skip[1][3] = 2. Diagonals and the long center crossings all map through skip[...][...] = 5.

The dfs(cur, remaining) function marks cur as visited, then tries every unused next key. A move to nxt is legal if there is no key in between (skip[cur][nxt] == 0) or the in-between key is already visited. When remaining hits 0 we have built one full pattern and return 1.

To avoid recomputing symmetric starts, the code counts from one corner (×4 for all corners), one edge (×4 for all edges), and the center once, since the 3×3 grid is symmetric.

Example: m = 1, n = 2. Length 1 gives 9 patterns and length 2 gives 56, so the total is 65.

Time: O(8! / (8-n)!) Space: O(n)