同じ点を複数回通れる場合の「パターンロック」のパターン数

Androidなどに採用されていてる、並んだ点同士を指でなぞって結ぶことにより、パスワードの代わりとする認証方法があります。正式名称は知らないのですが、とりあえずここでは「パターンロック」と呼ばせていただくことにします。

Androidのパターン数については既に計算している方がいます。
http://blog.goo.ne.jp/nihongi/e/d0cfde12d440b92c181b6afd2b7dc4cb
http://beust.com/weblog2/archives/000497.html

Androidでは一度通った点は再度通れないことになっています（上を通過するのはOK）。しかし、独自に認証を搭載したアプリで、同じ点を何回でも通れるようなパターンを設定できるものがありました。これのパターン数を知りたいという方がいましたので、数えてみました。
条件は、

• 隣接する上下・左右・斜め方向の動きで点を結べる
• 将棋の「桂馬」の動きのような結び方はなし
• 一度通った点も再度通れる
• 使える点は3x3の9個

です。

3x3の点で同じ点を複数回通れる場合の「パターンロック」のパターン数

結ぶ点の数	パターン数
1	9
2	40
3	200
4	952
5	4624
6	22272
7	107648
8	519552
9	2509056
10	12113920
11	58492928
12	282425344

結ぶ点の数が12個までを計算しましたが、同じ点を複数回通れるので結ぶ点の数はいくらでも増やせます。

Androidで一度通った点は再度通れないようにしているのは、UI上で通った点の軌跡を表示する都合上、同じ軌跡を2度描けないからだと思います。

私が見たアプリではUI上で通った点の軌跡を表示せず、通り方そのものを覚える方式であるため、複数回同じ軌跡を描くような通り方も設定可能になっていました。

たしかにUI上で軌跡を表示すればグラフィカルに記憶できますが、制限を外して自由にパターンを書けるようにしたほうがかえって覚えやすい場合もありますので一長一短ですね。

参考：Rubyによるプログラムのソース

以下に3x3の点がある場合のパターン数を計算するRubyスクリプトを示します。 実行時の引数に結ぶ点の数を指定するとパターン数を出力します。

#!/bin/ruby
# assume dots such as:
# a b c
# d e f
# g h i

class PatternLock
  def initialize
    @dots = {
      'a' => ['b', 'd' ,'e'],
      'b' => ['a', 'c' ,'d', 'e' ,'f'],
      'c' => ['b', 'e' ,'f'],
      'd' => ['a', 'b' ,'e', 'g' ,'h'],
      'e' => ['a', 'b' ,'c', 'd' ,'f', 'g' ,'h' ,'i'],
      'f' => ['b', 'c' ,'e', 'h' ,'i'],
      'g' => ['d', 'e' ,'h'],
      'h' => ['d', 'e' ,'f', 'g' ,'i'],
      'i' => ['e', 'f' ,'h'],
    }
  end

  protected
  def countPattern(level, dot)
    if (level <= 1) then
      return 1;
    else
      count = 0
      @dots[dot].each do |x|
        count += self.countPattern(level - 1, x)
      end
      return count
    end
  end

  public
  def getCount(length)
    count = 0
    @dots.each do |k, v|
      count += countPattern(length, k)
    end
    return count
  end
end

pl = PatternLock.new
puts pl.getCount(ARGV[0].to_i)

PatternLockクラスのインスタンス変数@dotsは、パターンに使える点をキーとし、次に結べる点の集合の配列を値に持つ連想配列です。上記例では各点にアルファベット1文字を割り当てています。@dotsを変更することで点の数が異なる場合や将棋の桂馬の動きを許可する場合なども計算できます。