别小看九宫格：一道安卓手势解锁题，暴露了多少程序员的搜索能力？

别小看九宫格：一道安卓手势解锁题，暴露了多少程序员的搜索能力？

作者：Echo_Wish

很多程序员第一次看到 LeetCode 351《Android Unlock Patterns（安卓手势解锁）》的时候，都会觉得：

“不就是九个点随便连吗？”

结果真正开始写代码后，发现根本没那么简单。

因为这道题表面上是在数手势密码数量，实际上考察的是：

状态搜索、路径约束、回溯剪枝以及图遍历思想。

更有意思的是，这道题特别像现实中的很多工程问题。

看似只有9个节点。

实际上每一步选择都会影响后面的所有可能。

这和我们设计系统架构、优化调度算法甚至做技术选型都很像。

局部最优很容易。

全局搜索才是真本事。

今天咱们就来聊聊这道经典题。

一、这题到底在说什么？

安卓早期的手势锁长这样：

1 2 3 4 5 6 7 8 9

用户可以通过滑动连接多个点形成密码。

例如：

1 → 2 → 3 → 6

或者：