晚饭时和同事聊到安卓屏幕解锁时会有多少种解锁方案，觉得很有趣，吃完饭开始想办法解题，花了大概2个小时解决。思路如下：
- 使用索引值0-9表示从左到右、从上到下的9个点，行、列号很容易从索引值得到；
- 使用一个列表（routeList）来表示解锁路径，列表的元素为点的索引值；
- 从任意点N出发（将index(N)放入routeList），判断与哪些点（集合NextNodes）可以构成合法路径；然后用递归的方式从NextNodes中的点出发，寻找下一个可以构成合法路径的点；直到再也无法找到可用的点供路径使用
下一步，就是在Nexus 7上捣鼓，发现Android定义合法的解锁路径必须满足下列条件：
- 构成路径的点不得少于4个
- 路径中不能有重复的点
- （这点有点绕口）构成边或对角线的两点（例如[0,2]构成边，[0,8]构成对角线），不能在路径中相邻，除非其中点已经在路径中出现
接下来就是写代码了，Let's talk with the code!
问题的解是：
###############################################################
####### AndrUlkComb.py #########
## Calculate the COMBination count for ANDroid UNLock screen ##
## By grepall@gmail.com ##
############################################################### ###############################################################
## The Android unlock screen looks like below
## -------------------------------
## o -> o -> o
##
## o o o
##
## o o o
## --------------------------------
##
## We'll use:
## 1. Index from 0-8 to represent all 9 nodes instead of
## using row:column format.
## 2. An array (routeList in the code) to record the path of the unlock combination.
## For example, for the unlock comb which is shown in
## in the figure. There will be 3 elements in the array:
## 0, 1, and 2. (Although it's NOT a valid path because of
## not long enough)
##
## Valid unlock path must holds true for 3 conditions:
## C1: It must pass 4 different nodes at least;
## C2: It cannot contains duplicate nodes;
## C3: This is a little tricky. Any node cannot direct link to another node, when
## any node will be past through if we connect those 2 nodes in the unlock panel. UNLESS
## the crossed node already EXISTs in the path.
## For example, path (0, 2, 5, 4) is not valid, because 0-->2 crosses node 1. But path
## (1, 0, 2, 5) is a vliad path.
## This rule holds for diagonal as well. #######################################################################
# M stands for the width of the unlock panel
# H stands for the height of the unlock panel
# CAUTION: Modify this value will NOT generate correct result!!! That's TO BE DONE
#
W = 3 #Width
H = 3 #Height # Unlock path
routeList = list() # Combination count, which is we want to know
routeCount = 0 def isValidRoute(p1, route):
# If the candidate node exists in the unlock path
if route.count(p1) != 0:
return False
return True; def isCrossPoint(p1, p2):
# Will the connection line (p1, p2) cross another node?
x1 = p1%W
y1 = p1/W
x2 = p2%W
y2 = p2/W
if x1 == x2 and abs(y1-y2) > 1:
return True # same column
if y1 == y2 and abs(x1-x2) > 1:
return True # same row
if abs(y1-y2) == abs(x1-x2) and abs(y1-y2)>1:
return True # diagonal
return False def tryPoint(lastPt, route):
# Try next valid node for the unlock path recursively
global routeCount
for pt in range(0, W*H):
if isValidRoute(pt, route): #C2
crossPt = (lastPt+pt)/2
if isCrossPoint(lastPt, pt) and route.count(crossPt) == 0: #C3
continue
route.append(pt)
if len(route) >3: #C1
routeCount += 1
tryPoint(pt, route)
route.pop() # Each node may be the start node for unlock
for i in range(0, W*H):
routeList = [i]
tryPoint(i, routeList)
print "Start from point %d, combination count is %d now..." % (i, routeCount)
print "Toatl combination counter for Android unlock screen: " + str(routeCount)