C++で解くAndroidパターンロック：解除パターンの総数を求めるアルゴリズム

問題概要

Androidスマートフォンでおなじみの3×3パターンロック画面を考えてみましょう。ここで、2つの整数 m と n(1 ≤ m ≤ n ≤ 9)が与えられます。このとき、m個以上n個以下のキーを使って描けるロック解除パターンの総数を求めるのが本記事の目的です。

パターンのルール

• 各パターンは、少なくともm個、最大でもn個のキーを結ぶ必要があります。
• 同じキーを複数回使うことはできません(すべてのキーは一意)。
• パターン内で連続する2つのキーを結ぶ直線が別のキーの上を通る場合、その通過されるキーはすでに選択済みでなければなりません。
• 未選択のキーをまたいで「ジャンプ」することは禁止されています。
• キーを選ぶ順序も意味を持つため、順序が異なれば別のパターンとして数えます。

たとえば、入力が m = 1、n = 1 の場合、出力は 9 になります。これは、どの1つのキー単体でもパターンとして成立するためです。

解き方のアプローチ

この問題は深さ優先探索(DFS)とバックトラッキングを組み合わせると効率的に解けます。ポイントとなるのは、あるキーから別のキーへ移動するときに「間に存在するキー」を記録しておくスキップテーブルです。

アルゴリズムの手順

1. 10×10のサイズの配列 skip を定義し、すべて0で初期化します。
2. 間に他のキーを挟むペアについて、その「間のキー」を設定します。
   • skip[1][3] = skip[3][1] = 2(1と3の間は2)
   • skip[1][7] = skip[7][1] = 4(1と7の間は4)
   • skip[3][9] = skip[9][3] = 6(3と9の間は6)
   • skip[7][9] = skip[9][7] = 8(7と9の間は8)
   • 対角線や中央を通る組み合わせ(1-9、3-7、2-8、4-6)は、すべて5を設定します。
3. DFS関数 dfs(node, len, visited) を定義します。

DFS関数の動作

• len が0になったら、1つのパターンが完成したので1を返します。
• visited[node] を true にします。
• i を1から9までループし、「i が未訪問」かつ「node と i の間にスキップすべきキーがない、またはそのキーがすでに訪問済み」の場合に dfs(i, len - 1, visited) を再帰呼び出しして結果を加算します。
• バックトラッキングのため、探索後に visited[node] を false に戻します。
• 結果 ret を返します。

対称性による最適化

メイン処理では、パターンの長さを m から n まで変えながらDFSを実行します。ここで重要になるのが盤面の対称性の活用です。

• 四隅のキー(1、3、7、9)は回転・反転によって互いに等価 → dfs(1, ...) の結果を4倍して加算
• 辺の中点のキー(2、4、6、8)も互いに等価 → dfs(2, ...) の結果を4倍して加算
• 中央のキー(5)は唯一の存在 → 結果をそのまま加算

この工夫により、全9キーを個別に起点として探索する必要がなくなり、計算量を大幅に削減できます。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int skip[10][10];
   int dfs(int node, int len, vector<bool>& visited){
      if (len == 0)
         return 1;
      visited[node] = true;
      int ret = 0;
      for (int i = 1; i <= 9; i++) {
         if (!visited[i] && (skip[node][i] == 0 || visited[skip[node][i]])) {
            ret += dfs(i, len - 1, visited);
         }
      }
      visited[node] = false;
      return ret;
   }
   int numberOfPatterns(int m, int n){
      memset(skip, 0, sizeof(skip));
      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[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[1][9] = skip[9][1] = 5;
      vector<bool> visited(10);
      int ret = 0;
      for (int i = m; i <= n; i++) {
         ret += (dfs(1, i - 1, visited) * 4);
         ret += (dfs(2, i - 1, visited) * 4);
         ret += dfs(5, i - 1, visited);
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfPatterns(1,1));
}

実行結果

入力

1, 1

出力

9

まとめ

Androidのパターンロックのような制約付き組み合わせ問題には、DFSとバックトラッキングの組み合わせが非常に有効です。さらに、盤面の対称性を利用して探索の起点を絞り込むことで、高速に答えを求められます。この手法は、ナイトツアーやNクイーン問題など、他のグリッド系パズルにも応用できる汎用的な考え方なので、ぜひマスターしておきましょう。