Android patterns possible on 3x3 matrix of numbers

https://www.quora.com/How-many-combinations-does-Android-9-point-unlock-have/answer/Yoyo-Zhou
Not only are nodes connected by adjacency and knight's moves; they can also connect via 2 steps along a line, or a peg jump, if the middle point is already used. That means the connectivity changes depending on what points have already been used.

So for example, if the nodes are labeled as

1 2 3

then (1 2 3), (2 1 3), (2 3 1), (3 2 1) could all be valid. (Note that these are all too short, since the minimum length is 4 points.)

The output of the code below is:

Sequences by length: [0, 0, 0, 0, 1624, 7152, 26016, 72912, 140704, 140704]
Total number of sequences: 389112

min_seq_length = 4

def Middle(a, b):
  """Return the node between a and b if there is one, or None."""
  if (a+b)%2 != 0:
    return None
  mid = (a+b)/2
  if mid == 5:
    return mid
  if a%3 == b%3:
    return mid
  if (a-1)/3 == (b-1)/3:
    return mid
  return None

def NextValid(base):
  """Generate valid moves j+1 given a sequence of moves 1..j."""
  if len(base) >= 9:
    return
  if len(base) == 0:
    for i in xrange(1,10):
      yield i
    return
  for i in xrange(1,10):
    if not i in base:
      mid = Middle(i, base[-1])
      if mid is None or mid in base:
        yield i

def Sequences(base):
  """Generator for valid sequences of moves."""
  if len(base) >= min_seq_length:
    yield list(base)
  for n in NextValid(base):
    for s in Sequences(base + [n]):
      yield s

seqs_of_length = [0]*10

for seq in Sequences([]):
  seqs_of_length[len(seq)] += 1
print 'Sequences by length:', seqs_of_length
print 'Total number of sequences:', sum(seqs_of_length)
https://www.quora.com/How-many-combinations-does-Android-9-point-unlock-have
http://stackoverflow.com/questions/12127833/patterns-possible-on-3x3-matrix-of-numbers

http://www.guokr.com/article/49408/

Android 的密码是 3 × 3 点阵中的一条路径，这条路径可以交叉，可以“走日字”，几乎是无所不能（只要不经过重复点），但却有一个例外：路径不允许跳过途中必须要经过的点。例如， 如果从左上角的点连接到右上角的点，中间的那个点会被自动地加进路径里。但麻烦就麻烦在，这个规则本身也有一个值得注意的地方：如果中间的点是之前已经用过的，那么这个点就可以被跳过去了。

我们不妨把点阵中的九个点分别用数字 1 到 9 编号。按照上述规则，4136、4192 都是不合法的，但 24136、654192 则都是可行的

包含 4、5、6、7、8、9 个点的合法路径数分别为 1624、7152、26016、72912、140704、140704
http://www.1point3acres.com/bbs/thread-148564-1-1.html
计算可能的 Android 解锁图案的个数。
限制条件：
i) 3x3 共九个点-google 1point3acres
ii) 最短图案包含 4 个点
iii) 最长图案包含 9 个点
iv) 路径不得跨越未访问的点，但是可以跨越访问过的点
例如， 0-2-6-8 就不合法（0-2 跨越了 1， 2-6 跨越 4， 6-8跨越了7）
0-1-2-4-6-7-8 或者 7-4-1-0-2-6-8 是合法的

0 1 2
3 4 5
6 7 8
http://www.cnblogs.com/EdwardLiu/p/5141771.html

1 2 3
4 5 6
7 8 9
只有中间没有其他键的两个键才能相连，比如1可以连 2 4 5 6 8 但不能连 3 7 9
但是如果中间键被使用了，那就可以连，比如5已经被使用了，那1就可以连9
每个键只能用一次，给定一个长度L，求问有多少unique path with length L

Backtracking: 我的code不光可以知道数目，还可以打印所有Pattern

 4 public class Solution {
 5     int res = 0;
 6     HashSet<Integer> set = new HashSet<Integer>();
 7     static ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 8     ArrayList<Integer> path = new ArrayList<Integer>();
 9     
10     public int calculate(int L) {
11         for (int i=1; i<=9; i++) {
12             set.add(i);
13         }
14         HashSet<Integer> visited = new HashSet<Integer>();
15         helper(0, 0, L, visited);
16         return res;
17     }
18     
19     public void helper(int cur, int pos, int L, HashSet<Integer> visited) {
20         if (pos == L) {
21             res++;
22             result.add(new ArrayList<Integer>(path));
23             return;
24         }
25         for (int elem : set) {
26             if (visited.contains(elem)) continue;
27             if (cur == 1) {
28                 if (elem==3 && !visited.contains(2)) continue;
29                 if (elem==7 && !visited.contains(4)) continue;
30                 if (elem==9 && !visited.contains(5)) continue;
31             }
32             else if (cur == 2) {
33                 if (elem==8 && !visited.contains(5)) continue;
34             }
35             else if (cur == 3) {
36                 if (elem==1 && !visited.contains(2)) continue;
37                 if (elem==7 && !visited.contains(5)) continue;
38                 if (elem==9 && !visited.contains(6)) continue;
39             }
40             else if (cur == 4) {
41                 if (elem == 6 && !visited.contains(5)) continue;
42             }
43             else if (cur == 6) {
44                 if (elem == 4 && !visited.contains(5)) continue;
45             }
46             else if (cur == 7) {
47                 if (elem==1 && !visited.contains(4)) continue;
48                 if (elem==3 && !visited.contains(5)) continue;
49                 if (elem==9 && !visited.contains(9)) continue;
50             }
51             else if (cur == 8) {
52                 if (elem==2 && !visited.contains(5)) continue;
53             }
54             else if (cur == 9) {
55                 if (elem==1 && !visited.contains(5)) continue;
56                 if (elem==3 && !visited.contains(6)) continue;
57                 if (elem==7 && !visited.contains(8)) continue;
58             }
59             visited.add(elem);
60             path.add(elem);
61             helper(elem, pos+1, L, visited);
62             visited.remove(elem);
63             path.remove(path.size()-1);
64         }
65     }
71     public static void main(String[] args) {
72         // TODO Auto-generated method stub
73         Solution sol = new Solution();
74         int res = sol.calculate(3);
75         System.out.println(res);
76         for (ArrayList<Integer> each : result) {
77             System.out.println(each);
78         }
79     }
81 }