Android Unlock Pattern

这个题一直以为是DP结果被吓住了，实际上这就是个跟数独和N皇后一样的穷举问题，通过枚举和检查来减少无效搜索，但是这道题的检查因为这个规则的复杂变成了最难的地方，而回溯的过程倒是无比简单，这里设置了一个-1初始位置来方便判断

class Solution(object):
    def numberOfPatterns(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        result = 0
        for i in xrange(m, n + 1):
            used = [False] * 9
            result += self.calPattern(-1, i, used)
        return result

    def calPattern(self, last, time, used):
        if time == 0:
            return 1

        result = 0
        for i in xrange(9):
            if self.check(last, i, used):
                used[i] = True
                result += self.calPattern(i, time - 1, used)
                used[i] = False

        return result

    def check(self, last, i, used):
        if used[i]:               # 已经被占用了则不行
            return False    
        if last == -1:            # 第一个位置自然没问题
            return True

        if (last + i) % 2:        # 前一个位置和当前选择位置如果构成马跳位或者相邻位合法
            return True
        mid = (last + i) / 2      # 找对角线末端的点
        if mid == 4:              # 如果前一个位置和当前位置跨过正中间的点，返回中间点的占用状态
            return used[mid]
        if i % 3 != last % 3 and i / 3 != last / 3:      # 同对角线上相邻的点
            return True
        return used[mid]

上面是完全穷举的方法，calPattern函数的时间复杂度是O(n!)，此题的1，3，7，9和2，4，6，8四个位置的结果实际上是均等的，我们可以只计算其中一个乘以4就可以优化计算