晚饭时和同事聊到安卓屏幕解锁时会有多少种解锁方案，觉得很有趣，吃完饭开始想办法解题，花了大概2个小时解决。思路如下：

1. 使用索引值0-9表示从左到右、从上到下的9个点，行、列号很容易从索引值得到；
2. 使用一个列表（routeList）来表示解锁路径，列表的元素为点的索引值；
3. 从任意点N出发（将index(N)放入routeList），判断与哪些点（集合NextNodes）可以构成合法路径；然后用递归的方式从NextNodes中的点出发，寻找下一个可以构成合法路径的点；直到再也无法找到可用的点供路径使用

下一步，就是在Nexus 7上捣鼓，发现Android定义合法的解锁路径必须满足下列条件：

• 构成路径的点不得少于4个
• 路径中不能有重复的点
• （这点有点绕口）构成边或对角线的两点（例如[0,2]构成边，[0,8]构成对角线），不能在路径中相邻，除非其中点已经在路径中出现

 

接下来就是写代码了，Let's talk with the code!

问题的解是：389112

 

1 ############################################################### 2  #######                   AndrUlkComb.py              ######### 3  ## Calculate the COMBination count for ANDroid UNLock screen ## 4  ##              By grepall@gmail.com                         ## 5  ############################################################### 6   7   8  ############################################################### 9  ## The Android unlock screen looks like below10  ## -------------------------------11  ##       o  ->  o  ->  o12  ##13  ##       o      o      o14  ##15  ##       o      o      o16  ## --------------------------------17  ##18  ## We'll use:19  ##  1. Index from 0-8 to represent all 9 nodes instead of20  ##      using row:column format.21  ##  2. An array (routeList in the code) to record the path of the unlock combination.22  ##      For example, for the unlock comb which is shown in23  ##      in the figure. There will be 3 elements in the array:24  ##      0, 1, and 2. (Although it's NOT a valid path because of25  ##      not long enough)26  ##27  ## Valid unlock path must holds true for 3 conditions:28  ##  C1: It must pass 4 different nodes at least;29  ##  C2: It cannot contains duplicate nodes;30  ##  C3: This is a little tricky. Any node cannot direct link to another node, when31  ##      any node will be past through if we connect those 2 nodes in the unlock panel. UNLESS32  ##      the crossed node already EXISTs in the path.33  ##      For example, path (0, 2, 5, 4) is not valid, because 0-->2 crosses node 1. But path34  ##      (1, 0, 2, 5) is a vliad path.35  ##      This rule holds for diagonal as well.36  37  38  39  #######################################################################40  # M stands for the width of the unlock panel41  # H stands for the height of the unlock panel42  # CAUTION: Modify this value will NOT generate correct result!!! That's TO BE DONE43  #44  W = 3   #Width45  H = 3   #Height46  47  # Unlock path48  routeList = list()49  50  # Combination count, which is we want to know51  routeCount = 052  53  54  55  def isValidRoute(p1, route):56      # If the candidate node exists in the unlock path57      if route.count(p1) != 0:58          return False 59      return True;60  61  62  def isCrossPoint(p1, p2):63      # Will the connection line (p1, p2) cross another node?64      x1 = p1%W65      y1 = p1/W66      x2 = p2%W67      y2 = p2/W68      if x1 == x2 and abs(y1-y2) > 1:69          return True # same column70      if y1 == y2 and abs(x1-x2) > 1:71          return True # same row72      if abs(y1-y2) == abs(x1-x2) and abs(y1-y2)>1:73          return True # diagonal74      return False75  76  def tryPoint(lastPt, route):77      # Try next valid node for the unlock path recursively78      global routeCount79      for pt in range(0, W*H):80          if isValidRoute(pt, route): #C281              crossPt = (lastPt+pt)/282              if isCrossPoint(lastPt, pt) and route.count(crossPt) == 0: #C383                  continue84              route.append(pt)85              if len(route) >3: #C186                  routeCount += 187              tryPoint(pt, route)88              route.pop()89  90  91  # Each node may be the start node for unlock92  for i in range(0, W*H):93      routeList = [i]94      tryPoint(i, routeList)95      print "Start from point %d, combination count is %d now..." % (i, routeCount)96  print "Toatl combination counter for Android unlock screen: " + str(routeCount)