スマホのパターンロックは何通り作れるのか気になったので、 Ruby でサクッと計算してみました。
- 使用する点の数ごとに何通りか
- 点の配置を通常の 3x3 でなく 3x5 や 4x4 に拡張したらどうなるか
先に計算結果
後述するコードで求めた、点の配置が W×H のときに k 点を使ったパターンの数を、以下の表に示します。
| k | 3x3 | 3x4 | 3x5 | 4x4 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 9 | 12 | 15 | 16 |
| 2 | 56 | 98 | 148 | 172 |
| 3 | 320 | 744 | 1,388 | 1,744 |
| 4 | 1,624 | 5,268 | 12,292 | 16,880 |
| 5 | 7,152 | 34,276 | 102,624 | 154,680 |
| 6 | 26,016 | 201,412 | 799,200 | 1,331,944 |
| 7 | 72,912 | 1,046,052 | 5,755,260 | 10,690,096 |
| 8 | 140,704 | 4,656,484 | 37,827,644 | 79,137,824 |
| 9 | 140,704 | 17,043,160 | 223,297,236 | 533,427,944 |
| 10 | 48,087,520 | 1,159,151,684 | 3,221,413,136 | |
| 11 | 93,100,144 | 5,143,990,352 | 17,068,504,632 | |
| 12 | 93,100,144 | 18,745,148,316 | 77,129,797,424 | |
| 13 | 52,666,905,476 | 285,415,667,080 | ||
| 14 | 101,695,562,512 | 811,404,606,344 | ||
| 15 | 101,695,562,512 | 1,577,602,537,520 | ||
| 16 | 1,577,602,537,520 |
3x3 に関しては各所にある値と同じでした。
4x4 はうまく検索できなかったものの、 1,577,602,537,520 で検索したら同じ値が求まっている記事が見つかりました（ 3x4 や 2x6 も）。本文の説明を見ると総当たりのようですが、何かしら高速化しているかもしれません。
- 石黒司, et al. モバイル端末のロック解除向けパターン認証の安全性評価. 研究報告コンピュータセキュリティ (CSEC), 2012, 2012.41: 1-6.
パターンのルール
Androidのヘルプには「指で簡単なパターンを描きます」としか説明が無かったので、ルールを纏めておきます。
- パターンロックとは、画面上の点を一筆書きでいくつか結ぶことで暗証番号（PIN）の代わりとする方式
- 結んだ点の「順序」によってパターンを区別する
- 同じ点を2回使うことはできない
- 点は9個あり、縦横 3x3 に等間隔で並んでいる
- 2点の間に他の点が存在し得る
-
2点を結ぶ際、その線分上にある他の点は使用済みでないといけない
- 未使用の点を指で避けて結んでも、自動的に間の点も通ったことになる
最後のルールが少し厄介そうです。2点を結べるかどうかというのは、簡単なグラフの問題なら辺の有無として始めから決まっていますが、今回のは事前に使った点に依存しています。この影響で例えば「点を逆順にしたパターンが作れない」といったことが起きます。
※ちなみに記事冒頭の画像のパターンは、「真上→左上→右上→真下」と作りました。逆順にできない一例です。
ルールを少し緩めて、パターンの総数の上界を見積もってみます。
2点を自由に結べる（間の点を飛び越すか選べる）場合、9点中 k 点を使って作れるパターンの総数は 9Pk = 9! / (9-k)! と計算できます（ふつうの順列）。スマホで許可されている最小の4点なら 9×8×7×6 = 3,024 通り、最大の9点なら 9! = 362,880 通りです。この程度なら実際に順列を列挙してそれぞれ制約を満たしているか検証する「総当たり」でも何とかなりそうです。
一方で今回は拡張したパターン（ 3x5 や 4x4 ）も考えたく、見積もりは大雑把に 16! ≒ 2.1×1013 なため、総当たりでは相当な時間がかかります。別の方法を検討します。
計算方針
以下では、点は横に W 個ずつ・縦に H 個ずつ並んでいるとします。点の総数は N = W×H です。
考え方
各点を順番に通る方法の探索というと巡回セールスマン問題（TSP）が思い浮かびます。この解法のひとつである Held–Karp algorithm （よくビットDPで実装されるもの）を真似ると、時間計算量は O(N2·2N) で済み、今回扱いたい N = 16 なら十分高速に解けます。
N 点中 k 点を使ったパターンというのは、 k-1 点を使ったパターンに線を追加することで作れます。新しい線を結べるかどうかはその2点（およびこれまで使った点）によって変わってくるので、パターンを数える際は「使用済みの点の集合」と「最後に使った点」で分類してテーブルに記録しておけば、線を追加したパターンを数えるのが楽になります。
例： 3x3 において、使った点が「左上・真上・右上・真下」・最後に使った点が「真下」のパターン数は、次のパターンを考えて合計すればいいです。
- 使った点が「左上・真上・右上」・最後に使った点が「左上」
- 使った点が「左上・真上・右上」・最後に使った点が「真上」 → 中央を使わないまま真上から真下へは線を結べないので除外
- 使った点が「左上・真上・右上」・最後に使った点が「右上」
それぞれの部分問題は使った点が少なくなっているので、再帰的に考えていけます。点が減ると同じ部分問題が繰り返し登場するようになるので、メモ化して計算を短縮します。
最も簡単なパターン（再帰の基本ケース）は「1点のみ使ったもの」で、 N 点それぞれに1通りあります。
※なお、数学的には「0点を使ったパターン」も1通り考えられますが、これには最後に使った点が存在しないため、考えているテーブルに記録できません。数えるときは特別扱いする必要があります。
2点を結べるかどうかの扱い
Held–Karp algorithm は、テーブルのインデックスとして「通った点の集合」を使っています。そのためパターンロックでこれから引く線が問題ないかどうかの判定に流用するのは簡単です。
基本的な巡回セールスマン問題では、任意の2点間の移動コスト（距離など）を2次元配列で持っています。今回はコストでなく2点を結ぶための条件：「どの点を使用済みでないといけないか」を集合で記録しておきます。こうすれば実際に2点を結ぶ際に、「使用済みの必要がある点の集合 ⊆ 使用済みの点の集合」を判定でき、ルールに沿わなければ数えないようにできます。
特に、比較する集合を bitset で表してあれば、集合の包含判定はビット演算ですぐ済みます。
# x が y の部分集合（ x ⊆ y ）かどうか判定する
x = 0b00101100 # { 2, 3, 5 }
y = 0b01101111 # { 0, 1, 2, 3, 5, 6 }
x & y == x #=> true
実装
競技プログラミングのように、標準入力から H W というふうに大きさを入力する形にしています。
前節では再帰で説明しましたが、本節のコードは非再帰でテーブルを下から埋めています。
H, W = gets.split.map!(&:to_i)
N = W * H # 点の個数
POW_N = 1 << N # 点の冪集合の個数 2**N
# 2点 i, j を結ぶ際に通過する点（の集合）を、全ての (i, j) の組について計算しておく
# （例） H, W = 5, 3 のとき、 passing_points[1][10] == 0b000_000_010_010_000
passing_points = Array.new(N) { Array.new(N, 0) }
[*0...N].repeated_permutation(2) do |i, j|
y_i, x_i = i.divmod(W)
y_j, x_j = j.divmod(W)
dx, dy = x_j - x_i, y_j - y_i
n = dx.gcd(dy)
next if n <= 1
bitset = 0
(1...n).each do |m|
x_k = x_i + dx / n * m
y_k = y_i + dy / n * m
k = x_k + y_k * W
bitset |= 1 << k
end
passing_points[i][j] = bitset
end
# パターン数を、使用した点の組合せ・最後の点で分類して記憶するテーブル
table = Array.new(POW_N) { Array.new(N, 0) }
# 基本ケースとして、1点のみを使ったパターン数を登録
(0...N).each { |k| table[1 << k][k] = 1 }
# 使用した点の少ないパターンから順に考える
# （とはいえbitsetの性質上、トポロジカルソートは保証されるので並べ替え不要）
(1...POW_N).each do |bitset|
# 使用済みの点 i から未使用の点 j へ線を引くことで新しいパターンを作れる
lasts, nexts = (0...N).partition { |k| bitset[k] == 1 }
lasts.product(nexts) do |i, j|
s = passing_points[i][j]
next if bitset & s != s # 通過する点が1つでも未使用なら線を引けない
table[bitset | 1 << j][j] += table[bitset][i]
end
end
# 求めたパターン数を、使用した点の数で集計する
counts = Array.new(N + 1, 0)
counts[0] = 1 # 0点は上のテーブルで表せないので別途登録
(1...POW_N).each do |bitset|
size = bitset.digits(2).count(1) # population count
counts[size] += table[bitset].sum
end
counts.each_with_index { |c, i| puts "#{i}: #{c}" }
Ruby には bitset クラスは無いので整数クラスで済ませています。整数クラスでも Integer#[] によって任意のビット範囲を切り出せる点が少し便利です（→リファレンス）。
計算結果は冒頭の表に示した通りです。