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

wayne

20# gogdizzy 我之前跟你有同样的质疑， 目前也还没深入看 无心大神的 代码,猜想是做了标记。 从跑的结果来看，无心人没有错，所以 能计算出所有合法的情况。

gogdizzy

21# wayne 跑了一下无心人的程序，结果中确实没有5 2 7 3 4 wayne确认一下这个序列是合法的吗？ 如果是合法的，那么就有可能你俩都错了。反倒是你之前给的结果数目较多，有可能正确。

wayne

22# gogdizzy 是合法的。 那我再看看我的代码

gogdizzy

我修改了一下无心人的代码，添加了一个next2的数组，这个数组用来查找跳跃关系， 例如next2[1]

= 3,2,3,5,9,4,7,0,0,0, 表示对于1，有3种跳跃可能，当2被mask了，就可以跳到3，当5被mask了，就可以跳到9，当4被mask了，就可以跳到7. 代码如下：

2. #include <stdio.h>
4. int mask[10] = {1,0,0,0,0,0,0,0,0,0};
5. int next[10][10] =
6. {0,0,0,0,0,0,0,0,0,0,
7. 5,2,4,5,6,8,0,0,0,0,
8. 7,1,3,4,5,6,7,9,0,0,
9. 5,2,4,5,6,8,0,0,0,0,
10. 7,1,2,3,5,7,8,9,0,0,
11. 8,1,2,3,4,6,7,8,9,0,
12. 7,1,2,3,5,7,8,9,0,0,
13. 5,2,4,5,6,8,0,0,0,0,
14. 7,1,3,4,5,6,7,9,0,0,
15. 5,2,4,5,6,8,0,0,0,0,
16. };
17. int next2[10][10] = {
18. 0,0,0,0,0,0,0,0,0,0,
19. 3,2,3,5,9,4,7,0,0,0,
20. 1,5,8,0,0,0,0,0,0,0,
21. 3,2,1,5,7,6,9,0,0,0,
22. 1,5,6,0,0,0,0,0,0,0,
23. 0,0,0,0,0,0,0,0,0,0,
24. 1,5,4,0,0,0,0,0,0,0,
25. 3,4,1,5,3,8,9,0,0,0,
26. 1,5,2,0,0,0,0,0,0,0,
27. 3,6,3,5,1,8,7,0,0,0,
28. };
31. int counter[10] = {0,0,0,0,0,0,0,0,0,0};
32. int graph[10] = {0,0,0,0,0,0,0,0,0,0};
33. int nextNumber = 0;
34. int graphPostion = 0;
36. void circle( int graphPostion )
37. {
38. int i, k;
39. int noPostion = 1;
40. int n = graph[graphPostion - 1];
41. for (i = 1; i <= next[n][0]; i ++)
42. {
43. if (mask[next[n][i]] == 0)
44. {
45. noPostion = 0;
46. mask[next[n][i]] = 1;
47. graph[graphPostion] = next[n][i];
48. counter[graphPostion + 1] ++;
49. printf( "find%d: ", graphPostion + 1 );
50. for( int z = 0; z < graphPostion + 1; ++z ) printf( "%d ", graph[z] );
51. puts( "" );
52. circle( graphPostion + 1 );
53. mask[next[n][i]] = 0;
54. }
55. }
57. for (i = 1, k = 1; i <= next2[n][0]; i ++, k += 2) {
58. if (mask[next2[n][k]] == 1 && mask[next2[n][k+1]] == 0 ) {
59. mask[next2[n][k+1]] = 1;
60. graph[graphPostion] = next2[n][k+1];
61. counter[graphPostion + 1] ++;
62. printf( "2find%d: ", graphPostion + 1 );
63. for( int z = 0; z < graphPostion + 1; ++z ) printf( "%d ", graph[z] );
64. puts( "" );
65. circle( graphPostion + 1 );
66. mask[next2[n][k+1]] = 0;
67. }
68. }
70. }
72. void first( void )
73. {
74. int i;
75. for (i = 1; i <= 9 ; i ++)
76. {
77. mask[i] = 1;
78. graph[graphPostion] = i;
79. counter[graphPostion+1] ++;
80. circle( graphPostion + 1 );
81. mask[i] = 0;
82. }
83. }
85. int main ( void )
86. {
87. int i;
88. first( );
89. for (i = 1; i <= 9; i ++)
90. printf("%d: %d\n", i, counter[i]);
91. return 0;
92. }

复制代码

最后运行结果： 1: 9 2: 56 3: 320 4: 1624 5: 7152 6: 26016 7: 72912 8: 140704 9: 140704 和你最开始给的答案一致。

wayne

24# gogdizzy 对16# 代码做了一点点的改动，跟楼上的gogdizzy 结果对上了，也跟我最开始的结果对上了。， 所以，我也知道我和无心人错在哪了。 有时候结果一致，不一定就是正确的哈，

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. n=3;ddd=Flatten[Table[{{i,j}},{i,0,n-1},{j,0,n-1}],1];
3. bb=Table[{ii,Product[n^2-k,{k,0,ii-1}],ddd=Select[Flatten[Table[Join[ii,List@#]&/@Complement[Flatten[Array[List,{n,n}]-1,1],ii],{ii,ddd}],1],Length[Complement[PointsToBeChecked[#[[-2;;-1]]],#[[1;;-3]]]]==0&];Length[ddd]},{ii,2,n^2}]

复制代码

wayne

gogdizzy , 有木有兴趣试试 4×4的情况

wayne

17# wayne 更正如下，求核对： 2,172 3,1744 4,16880 5,154680 6,1331944 7,10690096 后面的，我的改进版的程序也还是力不从心了， 在我2G内存的工作电脑上，Mathematica 抱怨：

1. No more memory available.
2. Mathematica kernel has shut down.
3. Try quitting other applications and then retry.

复制代码

gogdizzy

wayne 发表于 2013-6-24 16:34
gogdizzy ,
有木有兴趣试试 4×4的情况

哎，刚才试了一下，根本就算不过来，因为即使不考虑跳跃，每个数周围平均大概有10个可以连的。否则可能性更多，而最长的一条线应该是16个都用上，那就是10^15量级的搜索量，如果考虑跳跃，就是（10+x）^15了。我这里修改了一个通用程序，然后在circle里做了剪枝（超过一定长度就不计算了），结果如下：
1 : 16
2 : 172
3 : 1744
4 : 16880
5 : 154680
6 : 1331944
7 : 10690096
======添加一个结果=======
8 : 79137824
9 : 533427944
10 : 3221413136
11 : 17068504632     // 这个算了一个小时，再长一位可能又要增加10倍时间了。
12 : 77129797424
13 : 285415667080

程序代码：

1. #include <cstdio>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. #define  LEN  4
   
7. #define  PTS  (LEN * LEN)
   
8. 
   
9. int mask[PTS] = {0};
   
10. int counter[PTS+1] = {0};
    
11. int graph[PTS] = {0};
    
12. int neibNumber = 0;
    
13. int graphPostion = 0;
    
14. vector< int > neib[LEN][PTS];
    
15. 
    
16. int  gcd( int a, int b ) {
    
17.         int  t;
    
18.         while( b ) {
    
19.                 t = a % b;
    
20.                 a = b;
    
21.                 b = t;
    
22.         }
    
23.         return  a;
    
24. }
    
25. 
    
26. void  init_neib() {
    
27. 
    
28.         // init counter
    
29.         for( int i = 0; i < LEN; ++i )
    
30.                 for( int j = 0; j < PTS; ++j ) {
    
31.                         neib[i][j].clear();
    
32.                         neib[i][j].push_back( 0 );
    
33.                 }
    
34. 
    
35. #define  XY2IDX( r, c ) ( ( r ) * LEN + ( c ) )
    
36. #define  CHECK( r0, c0, r1, c1 ) \
    
37.         do {    int  rd = abs( r0 - r1 ); \
    
38.         int  cd = abs( c0 - c1 ); \
    
39.         int  gd = gcd( rd, cd ); \
    
40.         int  rs = ( r1 - r0 ) / gd; \
    
41.         int  cs = ( c1 - c0 ) / gd; \
    
42.         int  idx0 = XY2IDX( r0, c0 ); \
    
43.         int  idx1 = XY2IDX( r1, c1 ); \
    
44.         for( int i = 1; i <= gd; ++i ) neib[gd][idx0].push_back( XY2IDX( r0 + i * rs, c0 + i * cs ) ); \
    
45.         ++neib[gd][idx0][0]; \
    
46.         rs = -rs; cs = -cs; \
    
47.         for( int i = 1; i <= gd; ++i ) neib[gd][idx1].push_back( XY2IDX( r1 + i * rs, c1 + i * cs ) ); \
    
48.         ++neib[gd][idx1][0]; \
    
49.         } while(0)
    
50. 
    
51.         int  r0, c0, r1, c1;
    
52.         for( r0 = 0; r0 < LEN; ++r0 ) {
    
53.                 for( c0 = 0; c0 < LEN; ++c0 ) {
    
54.                         for( r1 = r0; r1 < LEN; ++r1 ) {
    
55.                                 for( c1 = ( r1 == r0 ? c0 + 1 : 0 ); c1 < LEN; ++c1 ) {
    
56.                                         CHECK( r0, c0, r1, c1 );
    
57.                                 }
    
58.                         }
    
59.                 }
    
60.         }
    
61. }
    
62. 
    
63. void  circle( int pos ) {
    
64.         if( pos > 6 ) return; // 剪枝了，计算量太大。
    
65.         int  i, j, k, step;
    
66.         bool ok;
    
67.         int  n = graph[pos-1];
    
68.         for( step = 1; step < LEN; ++step ) {
    
69.                 for( i = 0, k = 1; i < neib[step][n][0]; ++i, k += step ) {
    
70.                         ok = true;
    
71.                         for( j = 0; j < step - 1; ++j )
    
72.                                 if( mask[ neib[step][n][k+j] ] == 0 ) { ok = false; break; }
    
73.                         if( ok && mask[ neib[step][n][k+step-1] ] == 0 ) {
    
74.                                 mask[ neib[step][n][k+step-1] ] = 1;
    
75.                                 {
    
76.                                         graph[pos] = neib[step][n][k+step-1];
    
77.                                         counter[pos+1]++;
    
78.                                         circle( pos + 1 );
    
79.                                 }
    
80.                                 mask[ neib[step][n][k+step-1] ] = 0;
    
81.                         }
    
82.                 }
    
83.         }
    
84. }
    
85. 
    
86. void  first() {
    
87.         int  i;
    
88.         for( i = 0; i < PTS; ++i ) {
    
89.                 mask[i] = 1;
    
90.                 {
    
91.                         graph[graphPostion] = i;
    
92.                         counter[graphPostion + 1]++;
    
93.                         circle( graphPostion + 1 );
    
94.                 }
    
95.                 mask[i] = 0;
    
96.         }
    
97. }
    
98. 
    
99. void  print_vec( vector< int > & x ) {
    
100.         for( int i = 0; i < x.size(); ++i ) {
     
101.                 printf( "%d ", x[i] );
     
102.         }
     
103.         puts( "" );
     
104. }
     
105. 
     
106. int main ( void )
     
107. {
     
108.         init_neib();
     
109.         //for( int i = 1; i < LEN; ++i ) {
     
110.         //        for( int j = 0; j < PTS; ++j ) print_vec( neib[i][j] );
     
111.         //        puts( "" );
     
112.         //}
     
113.        
     
114.         first();
     
115.         for( int i = 0; i <= PTS; ++i ) {
     
116.                 printf( "%d : %d\n", i, counter[i] );
     
117.         }
     
118.         return 0;
     
119. }
     

复制代码

补充内容 (2013-7-2 09:31):
12 : 77129797424

补充内容 (2013-7-2 17:10):
代码里的counter数组用了int，会溢出，后来改成int64了。

补充内容 (2013-7-3 09:57):
如果考虑对称关系，可以提速。只需要计算1/8个象限内的起始点就可以了，当然因为对角线上的点必需计算，所以计算量略多于1/8。

补充内容 (2013-7-3 13:09):
13 : 285415667080          // 用了对称关系，所以这个结果也在几个小时内计算出来了。

wayne

gogdizzy 发表于 2013-7-1 15:15
哎，刚才试了一下，根本就算不过来，因为即使不考虑跳跃，每个数周围平均大概有10个可以连的。否则可能 ...

看到程序里的CHECK宏函数了，看来跟我的思路是一样的。

无心人

在我的代码里，不存在7-3的链接，
因为，7-3必定过5，是不存在的

不过我刚验证了你说的情况
可能是我还是没理解这个图案的禁断的判定吧