用老掉牙的技巧解决NP-难谜题。 原文：Intelligent brute forcing

背景简介

我读大学时玩过不少解谜游戏。这里的指的是非常特定的一类解谜游戏。比如：

很幸运，我在RPI（伦斯勒理工学院）上过数据结构这门课，这门课老师Cutler给学生留的学年作业/竞赛就是写一个解谜程序。每年的解谜游戏都不一样，而我那年的游戏则是Ricochet Robots，这个游戏其实就是多人游玩的推箱子游戏。我真的很享受这份作业（而且我还赢了比赛！），并且以助教的身份参加了这场比赛。好吧，啰哩啰嗦，回忆太多，希望不要搞得让人生厌了！

不管怎样，这份作业的目的是为了让所有人都熟悉递归和深度优先搜索。你写的程序需要给这个游戏一个初始状态，还要提供最大递归深度。游戏目标是，要么返回长度最短的可能解法，要么返回给定最小长度的所有可能的解法。至于竞赛，你加不加深度限制都可以，而且可能也会出现无解的情况。这堂课让我涨了不少知识获得了不少欢乐，所以也许你也需要来看一看。

抽象

我会在本文中给出一个新的解谜游戏，并展示我在写就快速且实际的解谜程序时使用到的技术。本文将涵盖深度优先搜索/A*搜索、记忆化、优化方法，以及处理NP-难和NP-完全问题的策略。如果你在此文中发现了任何问题或有改进方案，请在GitHub上想我提交PR或Issue。我在整个过程中都会以性能测试来验证我得出的结果。

译注记忆化即memoization，也是一种优化方法。