Android 锁密码组合

Question

我刚刚从我的同事那里听到了这个有趣的问题。我现在正在尝试，但同时我想我可以在这里分享。

Android 主屏幕上显示的密码网格中，可能有多少个有效密码？ 密码最小长度：4 最大：9（如果我错了请纠正我）

Answer 1

摘要

4 到 9 个独特数字的完整组合，减去包含无效“跳跃”的组合。

长版

Android 3x3 密码网格规则：

• 一次一点

• 不能“跳过”一个点

原帖作者使用 Mathematica 生成所有 985824 个组合。

因为没有“跳转”，所以几对连续的点都是无效的。

删除所有无效组合以达到结果。

4 到 9 点路径的组合分别为 1624、7152、26016、72912、140704、 140704.

中文原帖

参考来自guokr，一个类似 Stack Exchange Skeptics 的网站形式博客。

Answer 2

我知道这个问题很旧，但我在另一个 问题（在找到这个问题之前）在python中使用暴力方法，所以为了后代将其添加到这里：

pegs = {
    1: {3:2, 7:4, 9:5},
    2: {8:5},
    3: {1:2, 7:5, 9:6},
    4: {6:5},
    5: {},
    6: {4:5},
    7: {1:4, 3:5, 9:8},
    8: {2:5},
    9: {1:5, 3:6, 7:8}
}

def next_steps(path):
    return (n for n in range(1,10) if (not path or n not in path and 
                                       (n not in pegs[path[-1]] 
                                        or pegs[path[-1]][n] in path)))

def patterns(path, steps, verbose=False):
    if steps == 0:
        if verbose: print(path)
        return 1
    return sum(patterns(path+[n], steps-1) for n in next_steps(path))

这样你就可以列出任何数字的所有模式步骤数：

>>> [(steps, patterns([], steps)) for steps in range(1,10)]
[(1, 9),
 (2, 56),
 (3, 320),
 (4, 1624),
 (5, 7152),
 (6, 26016),
 (7, 72912),
 (8, 140704),
 (9, 140704)]
>>> sum(patterns([], steps) for steps in range(4,10))
389112

这不是解决该问题的最有效方法，因为您可以使用反射并仅计算 4*corner + 4*mid-edge + 1*middle，例如：

>>> patterns([], 6) == 4*patterns([1], 5) + 4*patterns([2], 5) + patterns([5], 5)
True

Answer 3

我通过递归搜索强行得到了答案，并找到了一个更大的答案，487272。算法很简单：尝试一切。我在这里引用了它。我没有在我的代码中发现任何错误（但我对c++不是很熟练）。抱歉有语法错误，我不是英语。

#include <iostream>
#include <stdlib.h>
using namespace std;

int combo;  //counter

void research(int Ipoints /*number of points already took*/, bool Icheck[9]/*points matrix*/,int Ilast/*last took point*/,
                   int Icomboval/*combination representation, only for printing purpose*/, int deep/*number of iteration, only for printing purpose*/)
{

    //  int numcall = 0;  //DEBUG


     for( int i=0; i<9; i++) //Controlling every free point in search of a valid way to contimue
          if( Icheck[i] == false )
          {  
              //Just for security, coping every variable in a new variable. I don't know how c++ works but I will make it works
              int points = Ipoints;
              int last = Ilast;
              int comboval = Icomboval;
              bool check[9];
                   for( int j=0; j<9; j++)
                        check[j] = Icheck[j];  

              int e1,e2;
              int middle = -1;
              e1=i; e2=last;  //Ccontrolling duble jumps
              if( e1 == 0 && e2 == 2 ) middle = 1;
              if( e1 == 3 && e2 == 5 ) middle = 4;
              if( e1 == 6 && e2 == 8 ) middle = 7;
              if( e1 == 0 && e2 == 6 ) middle = 3;
              if( e1 == 1 && e2 == 7 ) middle = 4;
              if( e1 == 2 && e2 == 8 ) middle = 5;
              if( e1 == 0 && e2 == 8 ) middle = 4;
              if( e1 == 6 && e2 == 2 ) middle = 4;

              e2=i; e1=last;  // in both way
              if( e1 == 0 && e2 == 2 ) middle = 1;
              if( e1 == 3 && e2 == 5 ) middle = 4;
              if( e1 == 6 && e2 == 8 ) middle = 7;
              if( e1 == 0 && e2 == 6 ) middle = 3;
              if( e1 == 1 && e2 == 7 ) middle = 4;
              if( e1 == 2 && e2 == 8 ) middle = 5;
              if( e1 == 0 && e2 == 8 ) middle = 4;
              if( e1 == 6 && e2 == 2 ) middle = 4;

              if((middle != -1) && !(check[middle])) {      
                        check[middle] = true;
                        points++;                      //adding middle points
                        comboval *= 10;
                        comboval += middle;
              }       

              check[i] = true;
              points++;           // get the point

              comboval*=10;
              comboval += i+1;

              if(points > 3)
              {
                  combo++; // every iteration over tree points is a valid combo

                // If you want to see they all, beware because printing they all is truly slow:
                    // cout << "Combination n. " << combo << " found: " << comboval  << " , points " << points << " with " << deep << " iterations\n";
              }

              if(points > 9)   //Just for sure, emergency shutdown,
              { exit(1); }


              research(points,check,i,comboval,deep+1); /*Recursive, here is the true program!*/

              // numcall++; //DEBUG
          }

       //   cout << "Ended " << deep << " , with " << numcall << " subs called\n";   // Only for debug purposes,remove with all the //DEBUG thing

}



int main ()
{
    combo = 0; //no initial knows combo
    bool checkerboard[9];
    for( int i=0; i<9; i++) checkerboard[i]=false; //blank initial pattern

    research(0/*no point taken*/,checkerboard,-1/*just a useless value*/,0/*blank combo*/,1/*it's the firs iteration*/); //let's search!

    cout << "\n"  ;            
    cout << "And the answer is ... " << combo << "\n"; //out

    char ans='\0';
    while(ans=='\0')
    {                   //just waiting
    cin >> ans;
    }

    return 0;
}

Answer 4

我只是运行 python 代码来获得可能的组合
我有 985824 种可能性

from itertools import permutations
numbers = "123456789"

total_combos = list(permutations(numbers,4))+list(permutations(numbers,5))+list(permutations(numbers,6))+list(permutations(numbers,7))+list(permutations(numbers,8))+list(permutations(numbers,9))
print(len(total_combos))

Answer 5

（点数 - 有效模式）
(4 - 746)
(5 - 3268)
(6 - 11132)
(7 - 27176)
(8 - 42432)
(9 - 32256)

---

共有 117010 个可能的有效模式