关于android手机图案锁屏的计数

wayne

应该有不少人知道android手机有一个图案锁屏的功能。
3×3的格子，一笔画，至少经过4个点，路径中重复经过的点不算入组成图案的有效的点集合，最终构成的一个图案 就可以锁屏了，注意还有方向哦～～


那么，这样的锁屏方式总共有多少种呢
=======
推广一下，要是n*n呢，一笔画 经历所有的点，有多少种？

hujunhua

不是P(9,4)+P(9,5)+P(9,6)+P(9,7)+P(9,8)+P(9,9)?

wayne

实不相瞒，我是在搜索 android图案锁屏 破解攻略的时候，顺带提出这个问题的。
来源：http://www.nfcous.com/?p=879

wayne

2# hujunhua
不对，老大，真实的答案应该比排列数要小很多的。

==========================
反例：假设我们将左上角的点标注(1,1)，向左向右坐标点递增， 那么不存在这样的4点的情况有很多，比如：

(1,1) -> (3,3) -> (1,3) -> (3,1)  (实质 是6个点，(1,1) ->(2,2)-> (3,3) ->(3,2)-> (1,3) -> (3,1))
(1,1) -> (3,3) ->(2,2) -> (1,3)   (这个不是一笔画)
(1,1) -> (1,3) ->(1,2) -> (3,3)   (这个也不是一笔画)
......

简而言之，就是多点共线的情形比较复杂：
1) 不能越过途中未标记的点，去标记新一点。
2) 每经历一个点，下一个点只可能是未标记的点，而不是已标记的点。

wayne

写了个程序，算出来得到：

{经过的点数，排列数，实际有效的一笔画种数}
{1, 9, 9},
{2, 72, 56},
{3, 504, 320}
{4,3024,1624},
{5,15120,7152},
{6,60480,26016},
{7,181440,72912},
{8,362880,140704},
{9,362880,140704}

1. PointsToBeChecked[{{a_,b_},{c_,d_}}]:=Module[{g=GCD[c-a,d-b]},If[g>1,{a+# (c-a)/g,b+# (d-b)/g}&/@Range[g-1],{}]];
   
2. CountOfPath[n_,k_]:=Module[{pp=Permutations[Flatten[Array[List,{n,n}]-1,1],{k}]},data=Select[pp,Sum[Length[Complement[PointsToBeChecked[#[[ii;;ii+1]]],#[[1;;ii-1]]]],{ii,Length[#]-1}]==0&];Length[data]];
   
3. CountOfPath[3,4]

复制代码

wayne

作出了图形，可供参考：
红色的点表示组成一笔画的点，黑色的表示不组成 一笔画的点。
左下角是坐标 {0,0}点。

算出3*3的图案，5个点的一笔画 可行的方案和不可行的方案，例子如：
可行的锁屏图案：
                             
不可行的锁屏图案：
                             

无心人

我正想提这个问题呢，
不想 wayne兄捷足先登，
并且算出来结果了

wayne

7# 无心人
我目前的算法 很老土，算n*n图案，k点的一笔画路径，总共有P(n^2,k) = n^2*(n^2-1)*(n^2-2)*...*(n^2-k+1) 种可能，
需要一个一个的验证

大神可否改进一下

无心人

迭代之？

然后，
写个跳跃表，表示当前点可以走到的点的集合

无心人

假设以左上角标示为1，先行后列，依次递增，为
1,2,3,4,5,6,7,8,9
则
1的下1跳可能是
2,4,5,6,8
表示成
1=>1,4,5,6,8