书名：程序设计竞赛训练营：算法与实践
ISBN：978-7-115-57984-3
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
编 著 邱 秋
责任编辑 秦 健
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书是以大学生程序设计竞赛为基础、面向已有C++入门知识且想要进一步学习的读者编写的C++进阶训练指南。全书分为回溯法、图、动态规划、网格等部分。回溯法部分介绍单向搜索和双向搜索，给出高级搜索的技巧；图部分分为图遍历和图算法章节，先介绍图遍历的方法，再以最小生成树问题、单源最短路径问题、多源最短路径问题、网络流问题中的经典算法为例，介绍了十余种算法的原理和相关应用；动态规划部分逐一介绍了集合型、区间型、图论型、概率型、非典型动态规划，并介绍了空间、时间上的优化技巧，以及相应的备忘、松弛技巧；网格部分作为独立的专题汇集了与网格相关的各种习题。
本书适合有意参加大学生程序设计竞赛的本科生、研究生阅读，对有意参加信息学奥林匹克竞赛的中学生具有参考价值。
子曰：“知之者不如好之者，好之者不如乐之者。”
——《论语·雍也》
人们常说“兴趣是最好的老师”。1998年，我还在高一的时候，就对计算机产生了浓厚的兴趣。那时计算机尚未全面普及，自己家庭条件也一般，根本无力购买“昂贵”的个人电脑，平时只能对着《电脑爱好者》[1]杂志上的广告，想象自己拥有一台个人电脑的情景。高中期间，每逢周末放假，我都要去县城的新华书店逛一逛，看看是否有新书可“免费”阅读。一次偶然的机会，看到书架上有一本《C语言教程》，我便不假思索买了下来并开始自学。那时候学校的微机室刚建立不久，上面只有最简单的QBasic，自己经常在上面尝试用QBasic语句编写一些小程序。有一次，在学习了高中物理的核裂变反应后，禁不住想使用QBasic编写一个程序来演示原子核的裂变反应。具体来说就是模拟中子撞击原子核，原子核分裂，释放出更多中子，这些中子继续撞击其他原子核……最终形成链式反应的过程。我用QBasic中的绘图函数绘制了一个小点表示中子，用较大的圆圈表示原子核，当中子碰到原子时，表示中子的小点消失，原子分裂为两个，释放一个中子，继续撞击其他原子。当程序最终调试运行成功，看着链式反应的图像逐渐展现的时候，自己的内心非常有成就感。作为一个编程爱好者，当看到自己的“作品”能够良好地运行或者解决某个编程难题时，那便是最开心和最自豪的“高光”时刻。
不过阴差阳错，我并未如愿选择感兴趣的计算机专业，而进入了医学院校，于是编程便成了我最大的业余爱好。在2011年的时候，我用了半年多的时间，完成了由Skiena和Revilla[2]合著的《挑战编程：程序设计竞赛训练手册》[1]一书的习题。在全部完成后，感觉书中每一章讲解部分的内容较为简略，使得中低水平的编程爱好者在读完各章节的内容后，难以获得足够的知识来解决相应章节的问题，因此打算写一本用C++来进行解题的参考书，以弥补上述不足。但是由于种种原因，一直没有下定决心来编写，这成为我的一个“心结”。一方面是市面上已经有很多关于算法和编程竞赛的图书，例如Skiena的The Algorithm Design Manual[2]、Sedgewick的Algorithms[3]、Halim的Competitive Programming[4]等，另一方面自己也没有足够的时间和精力去进一步深入学习算法，缺乏知识积累和写书的资料。不过非常幸运，从2015年11月开始，我终于有许多时间可以做这件事，于是本书逐渐写成。
本书以C++进行解题，读者对象是已经具备一定的C或者C++基础的编程爱好者，或者是准备参加程序竞赛正在进行训练的高中生，或者是期望通过学习算法和练习以获得进一步提高的大学生。代码采用GCC 5.3.0进行编译，使用C++11语言标准（需要启用编译符号：-std=c++11）。例题和练习以University of Valladolid Online Judge（UVa OJ）题库中题号100～1099的题目、Halim的Competitive Programming所介绍的习题以及本人在写作过程中解决的题目为基础，涵盖了绝大部分的基本算法。
考虑到篇幅限制，我将出版《程序设计竞赛训练营：基础与数学概念》《程序设计竞赛训练营：算法与实践》两本图书。本书包含回溯法、图遍历、图算法、动态规划、网格等章节，可以看作在《程序设计竞赛训练营：基础与数学概念》上的综合应用。回溯法本质上是暴力搜索，但根据题目条件的不同，可以应用剪枝技巧来提高程序运行效率，而动态规划则属于一种处理问题的技巧，它通过将已解决问题的解保存起来，避免重复解决子问题，从而提高效率。回溯法和动态规划都属于处理问题的一种策略。图遍历一章是各种图算法的基础，在图遍历的基础上可以衍生各种算法，从而能够解决多种问题，这也是既往编程竞赛考察的一个重要方面。图算法一章专门介绍了图论中经典问题的相应算法和具体应用。网格一章则介绍了以各种网格（矩形网格、三角形网格、棋盘、经纬度等）为问题背景，应用前述介绍的算法和策略来解决问题的技巧。
虽然一本书主要集中于基础和数学，另一本书主要集中于算法和技巧，但两本书的划分并不是绝对的。例如，在《程序设计竞赛训练营：基础与数学概念》中，介绍了KMP匹配算法、Aho-Corasick算法、扫描线算法、Graham扫描法、Jarvis步进法、Andrew合并法等，也介绍了诸如坐标离散化等处理问题的技巧。因此，有些练习所涉及的内容可能会跨越两本书的内容，请读者予以注意。
正如武术宗师的练成，如果不学习各种武术套路，建宗立派就如无根之木、无水之鱼，但是如果将武术套路学“死”，那就容易形成惯性思维，失去自己的创造性，更别谈创立新的武术流派。学习算法的最高境界，我认为和武术宗师的练成类似，既对各派的武功招数、优缺点了如指掌（就如同对基本算法的原理及实现非常熟悉），但又不囿于各派的武功路数（就像深刻理解了算法原理，掌握了算法的精髓所在），能够根据具体情况变通。不过本书并不是一本算法大全，并未将算法的所有细节介绍得面面俱到，只是摘录了要点，列出了关键所在，正所谓“师傅领进门，修行在自身”，需要读者在阅读本书的时候主动查阅相关资料并加以练习，以便进一步加深理解。古人云“授人以鱼，不如授之以渔”，我认为学习过程中最重要的是掌握学习的方法，而不是仅仅满足于某种具体算法的掌握，同时也不要被已经学习过的算法束缚了自己的想象力。
不言而喻，对于任何一道题目来说，“理解问题的解决过程”比“记住问题的解决过程”更为重要。解题的途径绝非只有书中所示例的一种。在理解问题的基础上，重新对问题进行定义，从某个新的角度再对原问题进行思考，激发解题的动力和突破既往解题思路的束缚，将已有的算法和数据结构知识予以重新组合，通过语言和编程技术使头脑中的想法变成计算机的实现代码，这样才能够在题目和编程解题间架设一座真正属于自己的桥梁[5]。我认为这是学习编程的过程中应该努力达到的一种更高境界。
感谢父亲[3]、母亲、妻子照顾家庭的辛劳付出，以及女儿、儿子对于我未能给予更多时间陪伴的理解，让我能够有时间专心思考，得以完成本书。阚元伟通读了本书的初稿，对行文上不连贯或描述有歧义的地方提出了修改意见，在此对其表示衷心的感谢。在本书编写的过程中，我参考了许多互联网上的资料和编程爱好者的博客文章，从他们的解题思路中得到了诸多启发，由于篇幅所限，不能在此一一列出致谢。正如散文家陈之藩在《谢天》中所写：“即是无论什么事，得之于人者太多，出之于己者太少。因为需要感谢的人太多了，就感谢天罢。”
由于本人水平有限，编写本书的过程，实际上也是一个不断自我学习和进步的过程，书中的谬误不当之处在所难免，敬请读者不吝指出，以便本书有机会再版时予以改进。如有任何意见或建议，请发送邮件到我的邮箱：metaphysis@yeah.net。
衷心希望读者在阅读本书的过程中能够独立思考，勤加练习，融会贯通，学有所得。祝解题愉快！
邱秋（寂静山林）
二〇二〇年一月一日于海南琼海
[1] 由中国科学院主管，北京《电脑爱好者》杂志社出版的一本日常计算机应用相关的杂志。
[2] 2018年7月，在与uDebug网站管理员Vinit Shah就UVa 12348 Fun Coloring的评测问题进行电子邮件交流的过程中，遗憾得知Miguel Ángel Revilla教授已于2018年4月去世。
[3] 在编著本书的过程中，由于工作的原因，父亲于2018年3月17日来海南帮忙照顾家庭。父亲有多年的高血压病史，海南天气炎热，使父亲血压控制得不理想，加之我对父亲的血压变化关注不够，且父亲自身对高血压可能导致的风险也未引起重视，长期服用降血压药物但未能规范检测血压变化……多种不利因素，导致父亲于2018年7月27日不幸去世，这让我心中深感愧疚，抱憾终生。
尽信《书》，则不如无《书》。
——《孟子·尽心下》
纸上得来终觉浅，绝知此事要躬行。
——陆游，《冬夜读书示子聿》
本书以计算机专业（或对ACM-ICPC竞赛感兴趣的其他专业）学生及编程爱好者为主要读者对象，也可以作为ACM-ICPC竞赛训练的辅助参考书。本书不是面向初学者的C++语言教程，要求读者已经具备一定的C或C++编程基础，有一定的英语阅读能力，了解基本的数据结构，已经掌握了初步的程序设计思想和方法，具备一定程度的算法分析和设计能力。本书的目标是引导读者进一步深入学习算法，同时结合习题来提高分析和解决算法问题的能力。
本书既是训练指南，又兼有读书笔记的性质。为了表达对Skiena和Revilla合著的《挑战编程：程序设计竞赛训练手册》一书的敬意（它激发了我对算法的兴趣，促使我编写这本书，可以说是让我对编程竞赛产生兴趣的“启蒙老师”），本书的章节名称参考了该书的目录解构，但章节编排、叙述方式和具体内容已“面目全非”。每章均以“知识点”为单元进行介绍，每个“知识点”基本上都会有一份解题报告（题目源于UVa OJ），之后再列出若干题目作为强化练习或者扩展练习。强化练习所给出的题目，一般只需要掌握当前所介绍的知识点就能予以解决。扩展练习所给出的题目，一般需要综合运用其他章节所介绍的知识点，甚至需要自行查询相关资料，对题目所涉及的相关背景知识及算法进行理解、消化、吸收后才能予以解决，其难度相对较高。
本书中英语姓名的汉译名参考李学军主编的《英语姓名译名手册》[6]。
本书各章习题的解题代码有两个版本，最初的版本于2011年上传至CSDN。2016年，对部分解题代码进行了修改完善，并对编码风格进行了若干调整，将其与已解决题目的代码合并，上传至GitHub[1]。由于UVa OJ上的评测数据可能已经发生了变化，个别涉及浮点数精度的代码在提交时可能会得到“Wrong Answer”的评判，但解题的基本思路是正确的，请读者酌情参考使用。
本书着重于算法的思想介绍和实现，一般不对算法的正确性给予证明。对正确性证明感兴趣的读者可参考标注的文献资料或者相关的专著，或者查阅“算法圣经”——Knuth的《计算机程序设计艺术》[7]及Cormen等人的《算法导论》[8]。参考文献或资料仅在第一次引用的时候给出标注，对于后续引用不再予以标注。
本书的所有题目中，除个别题目以外，其他题目均选自UVa OJ，因此不在每道题目前附加UVa以区分题目的来源。为了练习选择的便利，题目的右上角使用A～E的字母来标识此题的“相对难度”。以2020年1月1日为截止日期，按“解决该题目的不同用户数”（Distinct ACcepted User，DACU）进行分级：A（容易），DACU≥2000；B（偏易），1999≥DACU≥1000；C（中等难度），999≥DACU≥500；D（偏难），499≥DACU≥100；E（较难），99≥DACU。难度等级为A～C的题目建议全部完成，难度等级为D～E的题目尽自己最大努力去完成（对于某些尝试人数较少的题目，根据上述难度分级原则得到的难度值可能并不能准确反映题目的实际难度，本书适当进行了调整）。如果某道题的DACU较少，原因有多种：或者是该题所涉及的算法不太常见，具有一定难度；或者是输入的陷阱较多，不太容易获得通过；或者是题目本身描述不够清楚导致读题时容易产生歧义；或者是题目的描述过于冗长，愿意尝试的人较少[2]；或者是在线评测系统没有提供评测数据，导致无法对提交的代码进行评判[3]。不管是什么原因，你都应该尝试去解题。对于学有余力的读者来说，研读文献资料并亲自实现算法，然后用习题来检验实现代码的正确性，是提升能力素质的较好途径。
由于本书包含较多代码，为了尽量减少篇幅，每份代码均省略了头文件和默认的命名空间声明。为了代码能够正常运行，请读者直接下载GitHub上的代码，或者在手工输入的代码前增加如下的头文件和命名空间声明[4]：
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;对于使用GCC 5.3.0（或以上）版本编译器的读者，可以使用下述更为简洁的方式来包含所有头文件：
#include <bits/stdc++.h>本书中的算法实现旨在帮助读者理解算法，较多借助C++的标准模板库（Standard Template Library，STL），在运行效率和简洁性上可能并不是最佳的，建议读者在掌握算法后，自行尝试编写更为高效和简洁的算法实现作为自己的标准代码库（Standard Code Library，SCL）。
所有示例代码和参考代码均可从本书的配套资源获得。每个章节内属于同一节的示例代码按顺序排列，位于以章节编号命名的文件夹内。例如，本书1.1节的内容为“八皇后问题”，假设该小节包含多份示例代码，则按出现的先后顺序依次命名为1.1.1.cpp、1.1.2.cpp、1.1.3.cpp……如果只包含一份示例代码，则命名为1.1.1.cpp，均位于文件夹Books/PCC2/01内，文件命名在示例代码的第1行给出。
位于同一个文件中的、连续的示例代码采用如下的文件命名样式：
//------------------------------1.1.1.cpp------------------------------//
// 连续的示例代码。
//------------------------------1.1.1.cpp------------------------------//对应地，一些代码跨越正文的多个段落，这样的代码采用如下的文件命名样式：
//++++++++++++++++++++++++++++++1.1.1.cpp++++++++++++++++++++++++++++++//
// 跨越多个段落的示例代码（第1部分）。正文分隔了多个这样的示例代码片段，多个这样的片段构成了整个示例代码。
// 跨越多个段落的示例代码（第2部分）。
//++++++++++++++++++++++++++++++1.1.1.cpp++++++++++++++++++++++++++++++//[1] 读者可在GitHub搜索metaphysis/Code了解更多。
[2] 例如199 Partial Differential Equations。
[3] 例如510 Optimal Routing。
[4] 头文件``和``极少使用，未加入列表，不过它们在某些特定题目的示例代码中有应用。
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供编程题目解答的参考代码文件。
要获得以上配套资源，请在异步社区本书页面中单击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿。
如果您所在学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
路漫漫其修远兮，吾将上下而求索。
——屈原，《离骚》
在UVa OJ的在线题库中，有一部分题目无法通过直接模拟或者应用既定算法的方式来解决，而是需要搜索所有可能的情形以找到符合条件的解或者最优解，此时可以尝试使用回溯法（backtracking）解题。回溯法本质上是暴力搜索（brute force search），相当于在题目所蕴含的隐式图中进行深度优先遍历（Depth First Search，DFS），由于考虑了所有可能的情形，必定能够得到解，不过大多数情况下程序得到所有解的时间会比较长。由于计算机运算速率的大幅提高，在问题空间不是很大的情况下，通过回溯法往往都能够顺利将题目予以解决。更进一步地，对于某些特定的题目，可以预先生成所有解，然后再“打表”提交，而不一定总是“实时”计算问题的解。对于某些搜索空间较大的题目，还需要结合剪枝技巧来进一步缩小搜索空间，提高程序的运行效率，以便能够在规定的时间限制内获得解。
八皇后问题（eight queens puzzle）是回溯法中的一个经典入门问题。根据国际象棋的规则，在没有其他棋子阻挡的情况下，皇后能够攻击位于同一行、同一列、同一对角线上的对方棋子。如果在一个8 × 8的国际象棋棋盘上放置8个皇后，使得它们相互之间无法攻击对方，那么总共有多少种不同的放置方案呢？为了简化问题的讨论，关于棋盘对称的放置方法也视为不同的方案。图1-1给出了两种可行的放置方案。
图1-1 八皇后问题的两种可行放置方案
由于皇后攻击规则的特殊性，无法直接通过组合方法来计数可行的放置方案，而是需要通过遍历所有可能的放置位置来确定放置方案的数量。如前所述，回溯法相当于在隐式图中进行深度优先遍历，因此需要将题目中的约束条件转换成某种“状态”，这些“状态”和隐式图中的顶点一一对应[1]。对于当前“状态”，按照题目给定的规则，能够从当前“状态”衍生出若干后继“状态”，从当前“状态”转移到它的某个后继“状态”就相当于沿着隐式图中的一条有向边从一个顶点到达另外一个顶点。从整体来看，回溯是一个从“初始状态”出发，不断地在“状态”及其后继“状态”之间转移并逐步深入的过程。在此过程中，需要记录已经访问的“状态”，以免重复访问。回溯通过不重复的遍历，最终会达到“终止状态”——满足可行解部分（或全部）要求的一种状态，其所要满足的条件具体由题目所给的约束来确定。此时根据可行解所要满足的条件对“终止状态”进行检查，如果“终止状态”符合可行解的要求，则表明回溯过程找到了一个合法解，将其“记录在案”，接着从“终止状态”回退到上一层的“状态”继续进行搜索。在回溯过程中，可能某条遍历“路径”并不能到达“终止状态”，此时就需要立即回退到上一层的“状态”继续进行搜索。以八皇后问题为例，“状态”就是指棋盘的大小及已经放置的皇后数量和位置；“初始状态”就是8 × 8的空棋盘；“终止状态”就是8 × 8的棋盘上放置了8个皇后；对“终止状态”进行合法性检查就是检查已经放置的8个皇后是否满足“不能相互攻击”的约束条件。
考虑到棋盘是二维的，可以使用一个二维数组board来保存棋盘状态，board[i][j]为1表示在棋盘的第i行第j列放置了一个皇后，为0则表示此位置尚未放置皇后。如果按照朴素的方法逐个位置尝试皇后的放置位置，则由于每行有8个位置，总的搜索空间将是88 = 16777216种。但是进一步仔细分析的话，由于每一行和每一列只能有一个皇后，则第1行有8个位置可选，第2行有7个位置可选，第3行有6个位置可选……仅考虑避免行和列的攻击时，皇后的可选放置方案数为8! = 40320种，只需对这些放置方案进行对角线规则的验证，如果符合则是一种合法的放置方案，搜索空间明显减少。由此可以得到下述的八皇后问题回溯法解题框架。
// board记录具体的放置方案，clnUsed记录已经使用的列，cnt记录放置方案数。
int board[8][8] = {}, clnUsed[8] = {}, cnt = 0;
// 使用递归来实现回溯，参数row表示当前为第几行选择放置皇后的位置。从0开始计数行。
void dfs(int row)
{
// 递归的出口。
// 如果递归深度已经到达第8层，表明已经放置了8个皇后，此时可以结束递归。
// 检查当前放置方案是否满足“对角线”规则，如果满足则是可行解，将方案输出并计数。
if (row == 8) {
// checkBoard检查棋盘状态是否满足“对角线”约束，printBoard输出棋盘状态。
if (checkBoard()) { printBoard(); cnt++; return; }
}
// 枚举当前行的所有列，检查是否存在满足“行列”约束的列。从0开始计数列。
for (int cln = 0; cln < 8; cln++) {
// 检查该列是否已经被使用。
if (clnUsed[cln]) continue;
// 将未使用的列标记为已使用状态，同时记录放置皇后的位置。
clnUsed[cln] = 1, board[row][cln] = 1;
// 递归，进入下一行继续选择可以放置的皇后的列。
dfs(row + 1);
// 将已使用的列恢复为未使用状态，以便在递归回退时能够再次使用此列。
clnUsed[cln] = 0, board[row][cln] = 0;
}
}根据上述所给出的回溯法实现框架，应该不难编写一个完整的程序来解决八皇后问题。作为练习，请读者先尝试完成代码的编写并进行调试，然后再与后续给出的参考实现进行比较。需要注意，在回溯过程中，每使用一个对应候选位置都需要予以标记，以便后续将其值还原，为下次使用做准备，否则将导致“遗漏”部分搜索空间，从而无法得到所有可行解。
如何检查棋盘上放置的皇后是否满足对角线规则呢？朴素的方法是逐个枚举皇后所在位置两条对角线上的各个方格，检查这些方格中是否放置了皇后。显然，此种方法效率较低，更为巧妙的是使用对角线检查。如图1-2所示，在逐行给每个皇后选择列位置后，假设第1个皇后选择了第1列，第2个皇后选择了第4列，第3个皇后选择了第3列，此时第3个皇后与第1个、第2个皇后均存在对角线冲突。使用一维数组按行序记录皇后的列选择，可以表示为{1，4，3}，则第3个皇后和第1个皇后的行序号差的绝对值为2，等于两者选择的列序号3和1差的绝对值，同时第3个皇后和第2个皇后的行序号差的绝对值为1，与两者选择的列序号3和4的差的绝对值亦相等。可以证明，如果存在对角线冲突，则后续选择的皇后的列序号与已经选择的皇后的列序号差的绝对值会与其相应行序号差的绝对值相等，与之相反，如果绝对值不等，则肯定不存在对角线冲突。
图1-2 对角线检查
通过进一步地深入思考，还可以应用以下优化技巧。
（1）由于是逐行考虑皇后可以放置的列，实际上可以在状态选择记录时省去“行”这一维度，只记录列的选择，即将选择状态记录数组缩减为一维，而不是原来的二维。
（2）由于放置方案可能在回溯过程的中途就已经不满足对角线规则，若能够及早剔除这些“次品”，无疑会提高搜索的效率。可以在确定当前行所选列后立即进行对角线规则检查，而不是总在最后时刻才进行对角线规则检查。与此同时，只对当前行所选列和已选列之间进行对角线规则检查，而不必在所有已选列之间进行对角线规则检查。因为在之前的回溯中已经对这些已选列之间进行了对角线规则检查，不必再次进行检查。
//------------------------------1.1.1.cpp------------------------------//
const int MAXN = 8;
int board[MAXN] = {0}, clnUsed[MAXN] = {0}, cnt = 0;
// 检查当前行所选列与已选列是否满足对角线规则。
bool checkBoard(int row, int selected)
{
for (int cln = 0; cln < row; cln++)
if (abs(row - cln) == abs(selected - board[cln]))
return false;
return true;
}
// 输出放置方案，放置皇后的位置以‘Q’表示，未放置皇后的位置以‘*’表示。
void printBoard()
{
for (int row = 0; row < MAXN; row++) {
for (int cln = 0; cln < MAXN; cln++)
cout << (board[row] == cln ? " Q" : " *");
cout << '\n';
}
cout << '\n';
}
// 使用递归来实现回溯。
void dfs(int row)
{
// 当行数达到棋盘的最大行数时表明回溯发现了一个可行解。
if (row == MAXN) { printBoard(); cnt++; return; }
// 未达到棋盘最大行数，继续进行递归回溯。
for (int cln = 0; cln < MAXN; cln++) {
// 为当前行选择列后立即进行对角线规则检查。
if (clnUsed[cln] || !checkBoard(row, cln)) continue;
// 标记已选列，回溯进入下一层。
clnUsed[cln] = 1, board[row] = cln;
dfs(row + 1);
clnUsed[cln] = 0, board[row] = -1;
}
}
int main(int argc, char *argv[])
{
dfs(0);
cout << cnt << '\n';
return 0;
}
//------------------------------1.1.1.cpp------------------------------//以下是上述代码运行后的部分输出：
Q * * * * * * *
* * * * Q * * v
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
…
92由输出可知，在8 × 8的棋盘上放置8个皇后，只有92种放置方案符合要求，只占搜索空间的1/438左右。随着棋盘的增大，符合要求的放置方案占搜索空间的比例将进一步缩小，而搜索时间却大幅度增加，直至回溯法变得低效而不适用。
知识拓展
当
时，在n × n的棋盘上放置n个互不攻击的皇后的不同方法数对应于OEIS编号为A000170的数列（只列举了数列的前20项，方括号前为放置方案数，方括号内为棋盘的大小）：1[1]，0[2]，0[3]，2[4]，10[5]，4[6]，40[7]，92[8]，352[9]，724[10]，2680[11]，14200[12]，73712[13]，365596[14]，2279184[15]，14772512[16]，95815104[17]，666090624[18]，4968057848[19]，39029188884[20]，等等。
在前述八皇后问题的实现中，在为第r行选定皇后所能放置的列之后，需要从第0行遍历到第(r − 1)行进行对角线规则检查，其耗时随着r的增大而逐渐增加。由于每次选择列之后都需要进行一次这样的检查，累积起来是一笔不小的时间开销。能否通过某种方法快速确定不存在对角线冲突的可选列呢？答案是肯定的。可以通过位向量标记实现这个目标，从而达到优化程序提高效率的目的[9]。使用位向量标记的关键是如何使用位来表示已选列和可选列，考虑到为当前行选择某列会对后续行的可选列数量及位置产生影响，可以使用图1-3所示的方法来构造位向量。特别地，当n较小时（例如
），3个位向量可以使用3个int数据类型变量来代替。
图1-3 八皇后问题位向量的构造
注意
图1-3中，当在某行选择一个可行列放置皇后之后，会对紧接其后的一行立即产生了两个“禁止列”——所选择列的左侧一列和右侧一列。而且，每向后一行，前面已选列所产生的“禁止列”各向左（右）侧移动一个位置。如果令位向量M表示当前已经选择的列，位向量L表示已选列在左侧产生的“禁止列”，位向量R表示已选列在右侧产生的“禁止列”，那么后续行的可选列位置为3个位向量先进行“或”运算然后进行“取反”运算后仍为0的二进制位所对应的列，即可选列C为~(L | M | R)中为0的二进制位所代表的列。假设以8个二进制位表示列状态，最左侧的二进制位表示第1列，最右侧的二进制位表示第8列，则可以将回溯过程中前3行位向量的选择描述如下：（1）第1行，L = M = R = 00000000，则C = ~(L | M | R) = 11111111，共有8个位置可选，若选择第1列，则M = (M | 10000000) = 10000000；更新L = (L | 10000000) << 1 = 00000000，R = (R | 10000000) >> 1 = 01000000；（2）第2行：L = 00000000，M = 10000000，R = 01000000，则C = ~(L | M | R) = 00111111，有6列位置可选，若选择第3列，则M = (M | 00100000) = 10100000，更新L = (L | 00100000) << 1 = 01000000，R = (R | 00100000) >> 1 = 00110000；（3）第3行：L = 01000000，M = 10100000，R = 00110000，则C = ~(L | M | R) = 00001111，有4列位置可选，若选择第5列，则M = (M | 00001000) = 10101000，更新L = (L | 00001000) << 1 = 10010000，R = (R | 00001000) >> 1 = 00011100。依此类推，可继续为后续行选择可行列并更新相应的位向量。
由此可以得到以下优化的实现代码：
//------------------------------1.1.2.cpp------------------------------//
// n表示棋盘的大小。
int n;
// 递归实现回溯搜索。参数D为回溯的层次，L表示左侧的禁止列，M表示已选择列，R表示右侧禁止列。
int dfs(int D, int L, int M, int R)
{
// 回溯层次达到n表明这是一种符合要求的放置方案。
if (D == n) { cnt++, return; }
// 查找当前行的可选列。
for (int i = 0; i < n; i++)
// 通过位运算技巧选择可行列。
if (((1 << i) & (L | M | R)) == 0)
// 记录已选列、左侧禁止列、右侧禁止列，然后继续下一层回溯。
dfs(D + 1, (L | (1 << i)) << 1, M | (1 << i), (R | (1 << i)) >> 1);
}
//------------------------------1.1.2.cpp------------------------------//在上述代码片段中，还未彻底做到全部使用位运算。为了进一步挖掘位运算的提速潜力，可以将“查找当前行的可选列”这一环节也使用位运算来实现。与此同时，考虑到回溯到达第n层时，参数M的低n位必定全为1，只需检查参数M与低n位全为1的“特定标记”是否相等即可判定是否已经达到回溯的目标，这样可以省略表示递归深度的参数。由此可以得到下述进一步优化的实现代码：
//------------------------------1.1.3.cpp------------------------------//
// n为棋盘大小，cnt记录可行放置方案数，N_ONES为“特定标记”。
int n, cnt, N_ONES;
// N_ONES为低n位全为1的“特定标记”。
N_ONES = (1 << n) – 1;
// 使用递归实现回溯搜索。L表示左侧的禁止列，M表示已选择的列，R表示右侧的禁止列。
void dfs(int L, int M, int R)
{
int available, cln;
// 如果回溯已经达到第n层，则已选择列标记M的低n位必定全为1，会与标记N_ONES相等，
// 因此可以利用这个特点来判断是否已经成功放置了n个皇后。
if (M != N_ONES) {
// available表示当前可选列。
available = N_ONES & (~(L | M | R));
// 当available不为0时表示还有可选列。
while (available) {
// 利用位运算技巧得到available最右侧为1的位，表示当前可行的一种列选择。
cln = available & (~available + 1);
// 将已选择的列从可选列中剔除。
available ^= cln;
// 记录已经选择的列，左侧禁止列标记向左移一位，右侧禁止列标记向右移一位，继续回溯。
dfs((L | cln) << 1, M | cln, (R | cln) >> 1);
}
}
else cnt++;
}
//------------------------------1.1.3.cpp------------------------------//在最后一种实现中，充分利用了位运算的速度优势，因此在计算
时的棋盘放置方案时，速度较快。但由于n皇后问题本身的特殊性，随着棋盘的增大其搜索空间呈指数级增长，所以对于较大的n（例如
），位运算依然显得“力不从心”。
一名年迈的苏丹[2]没有儿子，因此她决定在去世的时候，将国家分成k个地区，每个地区由某个在指定测试中表现最佳的人来继承。由于可能出现单个人继承多个或全部地区的情况，她需要确保只有更高智商的候选人才能成为她的继任者，因此苏丹发明了一种特殊的测试方法。在一个喷泉幽鸣、暗香环绕的大厅里，放置了k个国际象棋棋盘，每个棋盘的方格均有一个1～99之间的数，同时给了8个宝石镶嵌的皇后棋子。每一个苏丹继任者候选人需要将8个皇后放置在棋盘上，使得它们不会互相攻击，同时8个皇后放置的方格内的数之和至少和苏丹已经给定的数一样大（对于不熟悉国际象棋规则的人来说，在放置时要求棋盘的每一行和每一列及对角线上都只能有一个皇后）。
编写程序读入棋盘及棋盘上的数字，确定在符合给定条件下所能得到的数字和的最大值（你心里明白苏丹不仅是一个国际象棋好手，同时也是一个优秀的数学家，因此你怀疑她给的数值可能是能够获得的最大数值）。
输入
输入第1行包含k值，后面是k组64个数组成的矩阵，每组有8行，每行8个数，给定的数均为正数且小于100。最多不超过20组棋盘。
输出
输出由k个数值组成，表示k组棋盘的数值和，以右对齐宽度5进行输出。
样例输入
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64样例输出
260分析
应用回溯法构建所有可能的放置方案，找到符合要求的放置方案，然后对各个放置方案求数值和，找到数值和的最大值。对于n皇后问题来说，使用回溯法解题，实际上是获得1～n的整数的所有排列中符合要求的特定排列。因此，对于本题中给定的棋盘规模来说，一种更为简便的方法是直接使用库函数中的next_permutation来生成1～8的所有排列而不需要“大动干戈”去具体实现回溯法。
强化练习
259 Software AllocationB，524 Prime Ring ProblemA，552 Filling the GapsD，677 All Walks of Length n From the First NodeC，750 8 Queens Chess ProblemA，932 Checking the N-Queens ProblemE，989 Su DokuC，10576 Y2K Accounting BugB，10957 So Doku CheckerD，11085 Back to the 8-QueensA，11195 Another n-Queen ProblemC。
扩展练习
653 GizilchD，1309 SudokuE[10]，10094 Place the GuardsC，10513 Bangladesh SequencesE。
提示
1309 Sudoku中，由于搜索空间较大，使用位运算优化的回溯法求解会超时，需要使用更为高效的回溯搜索算法。由于本问题实际上能够转化为精确覆盖问题，可以使用舞蹈链（dancing links）X算法高效求解，该算法为《计算机程序设计艺术》的作者Donald E. Knuth所发明，具体细节请读者参考Knuth为该算法所撰写的论文。注意，舞蹈链X算法本质上仍属于回溯算法，它的优点在于利用舞蹈链这种巧妙的数据结构加速了回溯状态的更改和还原，还能够通过在矩阵中选择包含最少元素1的列来减小在回溯的某个层次时的搜索分支数，能够以较高的效率求解精确覆盖问题，因此，可以用于高效地求解数独问题和n皇后问题。对于本题来说，解题的难点在于如何将问题约束转换为由0和1组成的矩阵。易知数独必须满足以下4个约束：（1）每个方格必须填写1～16中的一个数字；（2）每行必须填写1～16的数字一次且仅一次；（3）每列必须填写1～16的数字一次且仅一次；（4）每宫（4 × 4方格）必须填写1～16的数字一次且仅一次。那么转换得到的矩阵需要包含1024列：（1）第0列～第255列，如果某列c包含1，则表示在第c/16行第c%16列的方格填写了某个数字；（2）第256列～第511列，如果某列c包含1，则表示在第(c − 256)/16行填写了数字(c − 256)%16 + 1；（3）第512列～767列，如果某列c包含1，则表示在第(c − 512)/16行填写了数字(c − 512)%16 + 1；（4）第768列～第1023列，如果某列c包含1，则表示在第(c − 768)/16宫填写了数字(c − 768)%16 + 1。
10513 Bangladesh Sequences实际上是八皇后问题的扩展和变形，但是由于评测数据时间限制很紧，如果逐组数据计算，即使应用位运算优化技巧，仍然不能在限定时间内获得Accepted。根据题目所给定的条件，只有极少部分序列不是Bangladesh Sequences，例如，取n = 15，每个位置均为“?”，则不是Bangladesh Sequences的序列总数为32516。因此可以预先计算得到所有的非Bangladesh Sequences，再根据评测数据所给定的条件进行筛选，这样可以显著减少运行时间，从而获得Accepted。
对于n皇后问题，如果只需要求出一种可行的放置方案，可根据数学方法快速得到解[11]。设棋盘大小为n × n，要求在其上放置n个皇后且互相不能攻击，可按下述方法得到可行的放置方案（从第1行～第n行逐行给出放置皇后的列序号，从棋盘最左侧的列开始计数，即最左侧列的序号为1）。
若n mod 6≠2且n mod 6≠3，有
（1）若n为偶数，可放置的序号为2, 4, 6, 8, …, n, 1, 3, 5, 7, …, n − 1。
（2）若n为奇数，可放置的序号为2, 4, 6, 8, …, n − 1, 1, 3, 5, 7, …, n。
若n mod 6 = 2或者n mod 6 = 3，令k = n/2（除法为整除），有
（1）若k为偶数，n为偶数，可放置的序号为k, k + 2, k + 4, …, n, 2, 4, 6, …, k − 2, k + 3, k + 5, …, n − 1, 1, 3, 5, …, k + 1。
（2）若k为偶数，n为奇数，可放置的序号为k, k + 2, k + 4, …, n − 1, 2, 4, 6, …, k − 2, k + 3, k + 5, …, n − 2, 1, 3, 5, …, k + 1, n。
（3）若k为奇数，n为偶数，可放置的序号为k, k + 2, k + 4, …, n − 1, 1, 3, 5, …, k − 2, k + 3, k + 5, …, n, 2, 4, 6, …, k + 1。
（3）若k为奇数，n为奇数，可放置的序号为k, k + 2, k + 4, …, n − 2, 1, 3, 5, …, k − 2, k + 3, k + 5, …, n − 1, 2, 4, 6, …, k + 1, n。
//------------------------------1.1.4.cpp------------------------------//
// n皇后问题可行解快速构造。
// 数组clnAtRow保存的是各行放置皇后的列序号（从棋盘最左侧开始计数列，行和列均从0开始计数）。
void nQueen(int *clnAtRow, int n)
{
if (n % 6 != 2 && n % 6 != 3) {
int row = 0;
for (int y = 2; y <= n; y += 2) clnAtRow[row++] = y - 1;
for (int y = 1; y <= n; y += 2) clnAtRow[row++] = y - 1;
} else {
int k = n / 2;
int intervals[2][4][2] = {
{{k, n}, {2, k - 2}, {k + 3, n - 1}, {1, k + 1}},
{{k, n - 1}, {1, k - 2}, {k + 3, n}, {2, k + 1}}
};
int row = 0;
for (int x = 0; x < 4; x++) {
int start = intervals[k % 2][x][0], end = intervals[k % 2][x][1];
for (int y = start; y <= end; y += 2)
clnAtRow[row++] = y - 1;
}
if (n % 2) clnAtRow[row++] = n - 1;
}
}
//------------------------------1.1.4.cpp------------------------------//幻方（magic square）是指将1, 2, …, n2填入一个n × n的方阵，使得方阵的每一行、每一列、两条对角线上的数字和均相等，其中n称为幻方的阶（order）。数学家已经证明，对于任意n＞2，均存在对应的幻方。幻方中同一行数字相加得到的和M称为幻数（magic constant），其值的大小只和阶有关，且
朴素的方法是使用回溯法来搜索可能的数字组合，然后检查其是否构成幻方，不过这样做效率不高。有趣的是，人们发现可以使用固定的策略来构造幻方。根据幻方的阶，可以将其分为以下3种情形进行构造。
（1）奇数阶幻方的构造，其中n = 2k + 1，
。可以使用一种称为Siamese法（又称De la Loubère法或阶梯法）的策略来构造奇数阶幻方。具体步骤为：将1填入方阵第一行的中间一列，视方阵的第一行和最后一行、第一列和最后一列连续（即将方阵的上下和左右看成是相连的），对于后续的每一个数y，将其放置在前一个数x的右上角（亦即行数减1列数加1的位置）。如果按照前述策略所确定的位置上已经有数存在，则将需要放置的数y置于x的正下方，继续幻方的构造。读者可以观察图1-4所示的三阶幻方构造过程来获得更为直观的理解。
图1-4 三阶幻方构造
//++++++++++++++++++++++++++++++1.1.5.cpp++++++++++++++++++++++++++++++//
const int MAXN = 32;
// n = 2 * k + 1，k >= 1。
void fillMagic(int n, int magic[][MAXN])
{
for (int i = 0, j = n / 2, k = 1; k <= n * n; k++) {
magic[i][j] = k;
if (k % n) {
i = (i - 1 + n) % n;
j = (j + 1) % n;
}
else
i = (i + 1) % n;
}
}（2）双偶数阶幻方的构造，其中n = 4k，。首先定义“互补”的概念，如果两个数字的和等于n阶幻方的最大数字和最小数字的和，则称这一对数关于n阶幻方互补，例如8 + 57 = 65 = 64 + 1，则称8和57关于八阶幻方互补。在构造双偶数阶幻方时，先将1～n2的数按照行优先顺序填入方阵中，然后将整个方阵从左上角开始，划分为k2个4 × 4的子方阵，如果某个数位于子方阵的主、副对角线，则将其替换为与之互补的数，其实际效果相当于将这些数关于整个方阵进行中心对称的位置对调，亦即将位于方格(i, j)的数与位于方格(n − 1 − i, n − 1 − j)的数交换，其中，(i, j)必须是位于子方阵主、副对角线上的方格。读者可观察图1-5所示的八阶幻方构造来获得更为直观的理解。
const int MAXN = 32;
// n = 4 * k， k >= 1。
void fillMagic(int n, int magic[][MAXN])
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (((i % 4 == 0 || i % 4 == 3) && (j % 4 == 0 || j % 4 == 3)) ||
((i % 4 == 1 || i % 4 == 2) && (j % 4 == 1 || j % 4 == 2)))
magic[i][j] = n * n - (i * n + j);
else
magic[i][j] = i * n + j + 1;
}图1-5 八阶幻方构造
（3）单偶数阶幻方的构造，其中n = 4k + 2，。此种情形的幻方构造稍复杂。其步骤是：（a）将整个方阵划分为4个大小为(2k + 1) × (2k + 1)的子方阵，按照左上、右下、右上、左下的顺序依次使用Siamese法填充这4个奇数阶子幻方，按照顺序，相邻两个子幻方的对应元素值相差n2/4；（b）对于第0列～第(n/4 − 1)列、第(n − n/4 + 1)列～第(n − 1)列，将这些列位于第i行的数与第(i + n/2)行的数对换，其中，
；（c）在前述对换过程中，有两个方格(n/4,0)和(n/4,n/4)，前者不应对换却发生了对换，后者应该对换但未发生对换，需要予以特殊处理。读者可观察如图1-6～图1-8所示的十阶幻方构造来获得更为直观的理解。
图1-6 按Siamese法构造十阶幻方的奇数阶子幻方
图1-7 十阶幻方的对换
图1-8 特殊情况处理及最后构造完毕的十阶幻方
const int MAXN = 32;
// 幻方构造辅助填充函数。
void fillHelper(int n, int offseti, int offsetj, int offsetk, int magic[][MAXN])
{
for (int i = 0, j = n / 2, k = 1; k <= n * n; k++) {
magic[i + offseti][j + offsetj] = k + offsetk;
if (k % n) {
i = (i - 1 + n) % n;
j = (j + 1) % n;
}
else
i = (i + 1) % n;
}
}
// n = 4 * k + 2， k >= 1。
void fillMagic(int n, int magic[][MAXN])
{
// 使用Siamese方法填充4个子方阵。
fillHelper(n / 2, 0, 0, 0, magic);
fillHelper(n / 2, n / 2, n / 2, n * n / 4, magic);
fillHelper(n / 2, 0, n / 2, n * n / 2, magic);
fillHelper(n / 2, n / 2, 0, n * n / 4 * 3, magic);
// 对换。
for (int i = 0; i < n / 2; i++)
for (int j = 0; j < n / 4; j++)
swap(magic[i][j], magic[i + n / 2][j]);
for (int i = 0; i < n / 2; i++)
for (int j = n - n / 4 + 1; j < n; j++)
swap(magic[i][j], magic[i + n / 2][j]);
// 特殊情况处理。
for (int j = 0; j <= n / 4; j += n / 4)
swap(magic[n / 4][j], magic[n / 4 + n / 2][j]);
}
//++++++++++++++++++++++++++++++1.1.5.cpp++++++++++++++++++++++++++++++//强化练习
1266 Magic SquareD，10087 The Tajmahal of ++Y2kD。
如前所述，回溯法实质上是利用深度优先遍历的思想对隐式图所表示的问题空间进行一次穷尽搜索，这种穷尽搜索类似于“大海捞针”（look for a needle in a haystack），但它是一种有序的过程，最终是将所有可能作为解的候选答案进行了一遍检查，从而将符合要求的解筛选出来。一般情况下，可以直接应用回溯法解决的题目所涉及的问题空间都相对较小，按照既定的回溯法步骤均可以在规定时限内完成。
对于某些回溯类题目来说，使用回溯法进行搜索的过程是一个单向的过程，即从初始状态往目标状态搜索，则称之为单向搜索。单向搜索根据其使用方式又可以将其划分为以下的若干子类型。
在某些情形下，回溯法需要从初始状态出发，通过逐步构建解的方式直到达到解所具有的数量限制（例如，长度、高度、宽度、字符数），而在构建解的过程中，可能还需要满足一些约束（例如，相邻字符不能相等，数组的和为负数），在最后还可能对候选解再加以进一步地检查，以查看其是否符合一些其他限制条件。由于此类回溯法搜索了所有可能的解，故将其归类为完全搜索。
给定宽度为2，高度为1的若干枚多米诺骨牌，每枚多米诺骨牌牌面上有两个数字。将两枚多米诺骨牌固定放置在一行的两端，在中间留下n块宽度为2的空白，再给定m枚多米诺骨牌，请问是否可从m枚骨牌中选出某些骨牌填满这n块空白，并且使得相邻骨牌连接处的数字相同。例如，给定初始骨牌(0，1)和(3，4)，中间留有3块宽度为2的空白，4枚候选骨牌为(2, 1)、(5, 2)、(2, 2)、(3, 2)，则可以按如下方式进行填充：
(0, 1)(1, 2)(2, 2)(2, 3)(3, 4)输入
输入包含多组测试数据。每组测试数据的第1行为整数n，表示空白的块数，接着一行是整数m，表示候选骨牌的数量，
。接着两行表示两端的固定骨牌，每行包含两个整数，数字出现的顺序为固定骨牌上的数字，顺序为从左至右。接着是m行，也是每行包含两个整数，表示候选骨牌上的数字。当n为0时，输入结束。
输出
对于输入中的每组数据，如果存在满足要求的放置方案，输出YES，否则输出NO。
样例输入
3
4
0 1
3 4
2 1
5 6
2 2
3 2
0样例输出
YES分析
题目要求从m枚骨牌中选出n枚排成一行，使得起始和结尾数字与指定的数字相匹配，且相邻骨牌连接处的数字相同，很明显，必须搜索全部问题空间来筛选符合要求的解。但是直接应用生成全排列的方法来构造从m枚骨牌中选出n枚骨牌的所有排列，其数量较大，而且只能在生成排列后才能进行检查，不利于应用“相邻骨牌连接处的数字相同”这个限制条件。故按以下步骤进行回溯。
（1）确定回溯的初始状态和终止状态。由于是要求“相邻骨牌连接处的数字相同”，那么就从此入手，将连接处的数字视为状态，初始状态即为给定的位于最左侧的固定骨牌的右侧数字，终止状态即为给定的位于右侧固定骨牌的左侧数字。例如，在样例输入中，初始状态为1，终止状态为3。
（2）根据当前状态和候选骨牌进行回溯。由于初始状态为1，那么需要确定候选骨牌中是否有一侧数字为1的骨牌可用，如果有这样的骨牌未使用，则将其标志为已使用状态，因为候选骨牌只能被使用一次，后续不能再次使用。找到符合要求的骨牌后，回溯进入下一层，对应的状态将改变为已使用骨牌的对侧数字，已填充的空白块数加1。需要注意的是，在本题中候选骨牌是可以翻转使用的，如骨牌(2, 3)可作为(3, 2)使用，但数字相同的骨牌翻转使用效果相同，为了不增加回溯的深度，可以预先判断并予以剔除。
（3）确定是否达到终止状态。当回溯的深度达到预期时，需要对解进行检查，查看其是否符合题意要求。在本题中，当填满的空格块数达到n时，需要检查当前状态，即骨牌末尾处的数字是否和终止状态的数字相同。如果相同，表明找到了符合要求的骨牌排列方案，否则此搜索分支应该停止。为了减少不必要的搜索，在找到符合要求的方案后，可以设置完成标识以便尽早退出回溯过程。
参考代码
int n, m, dominoes[15][2], used[20];
int dot1, dot2, head, tail;
int finished = 0;
void dfs(int depth, int ending)
{
// 已经得到解，尽早退出。
if (finished) return;
// 回溯达到预定深度，检查解是否符合要求。
if (depth == n) {
if (ending == tail) finished = 1;
return;
}
// 回溯未达到预定深度，根据限制条件改变回溯状态并进入下一层回溯。
for (int i = 0; i < m; i++) {
if (used[i]) continue;
if (dominoes[i][0] == ending) {
used[i] = 1;
dfs(depth + 1, dominoes[i][1]);
used[i] = 0;
}
if (dominoes[i][0] != dominoes[i][1] && dominoes[i][1] == ending) {
used[i] = 1;
dfs(depth + 1, dominoes[i][0]);
used[i] = 0;
}
}
}
int main(int argc, char *argv[])
{
while (cin >> n, n > 0) {
// 读入初始状态、终止状态、候选骨牌。
cin >> m;
cin >> dot1 >> dot2; head = dot2;
cin >> dot1 >> dot2; tail = dot1;
for (int i = 0; i < m; i++) cin >> dominoes[i][0] >> dominoes[i][1];
// 回溯并输出解。
memset(used, 0, sizeof(used));
finished = 0;
dfs(0, head);
cout << (finished ? "YES" : "NO") << '\n';
}
return 0;
}强化练习
148 Anagram CheckerB，193 Graph ColoringA，211 The Domino EffectD，347 Run Run Runaround NumbersB，399 Another Puzzling ProblemD，416 LED TestB，441 LottoA，604 The Boggle GameC，843 Crypt KickerB，868 Numerical MazeD，996 Find the SequenceE，1052 Bit CompressorE，1262 PasswordC，10001 Garden of EdenC，10063 Knuth’s PermutationB，10186 Euro Cup 2000D，10202 Pairsumonious NumbersB，10344 23 Out of 5A，10637 CoprimesC，10950 Bad CodeD，11201 The Problem of the Crazy LinguistD，11961 DNAD，13004 At Most TwiceD。
扩展练习
165 StampsB，179 Code BreakingD，205 Getting ThereE，225 GolygonsD，265 Dining DiplomatsE，283 CompressE，387 A Puzzling ProblemD，592 Island of LogicD，10624 Super NumberC，10923 Seven SeasD，11471 Arrange the TilesD，11753 Creating PalindromeD。
提示
1052 Bit Compressor中，在解题时，需要准确理解题目描述中的约束条件“Replace any maximal sequence of n 1’s with the binary version of n whenever it shortens the length of the message.”。
10624 Super Number在UVa OJ上的评测数据较弱，使用单纯的回溯法可以在限制时间内获得通过。似乎没有特别有效的剪枝方法来提高效率，可以采取的措施有：（1）在进行模运算判断是否能够整除时，先使得被除数尽可能大，再一次性求模，这样可以减少求模运算的次数从而提高效率（具体来说就是只要被除数不超过long long int数据类型的表示范围，就暂不进行模运算）；（2）预先生成每个数位可能包含的数字而不是从0～9枚举，因为除1以外，能够被i所整除的数其末位不会取遍0～9。由于题目所给定的数据范围较小，也可以预先生成所有可能的解，然后使用查表的方式来获得Accepted。
10923 Seven Seas中，敌方战舰的移动规则：向距离己方战舰平面欧几里得距离最小的方格移动。需要高效地表示战舰和礁石的位置状态，否则容易超时。
11471 Arrange the Tiles中，将同类型的滑块合并可以减小搜索空间，从而能够更快地得到解，否则容易超时。
在完全搜索类型的回溯中，一个难点是如何记录回溯的状态和根据当前状态决定下一步回溯的选择。由于很多回溯类题目的背景都是在矩阵中进行，而矩阵由单元格组成，因此可以设置一个二维数组来标记当前单元格是否已经被使用。有时仅仅标记单元格是否被使用尚不足够，因为回溯状态可能具有方向性，在某个单元格的向左方向已经被使用，还可以选择向右的方向，因此可能要同时记录单元格的位置和被使用的方向，需要三维甚至四维数组来记录回溯的当前状态。
给定一个m × n的迷宫，迷宫由印有图案的方形木块组成，图案包括3种，如图1-9所示。
图1-9 印有图案的3种方形木块
你可以对木块进行旋转，但不能将木块移动到其他方格。给定迷宫的初始状态，确定有多少种不同的木块排列方式，使得木块上的图案能够形成连续的线段，连接左上角和右下角的单元格。图1-10给出了初始的木块排列和满足要求的一种木块排列方式。
图1-10 初始及满足要求的木块排列方式
输入
输入第1行为一个整数c，表示测试数据的组数。每组测试数据第1行包含两个整数m和n，表示迷宫的行数和列数。接着是以ASCII表示的迷宫，由“+”“-”“*”“|”和空格构成。迷宫大小满足
的限制。
输出
对于输入中的每组测试数据，输出一个整数，表示满足要求的不同路径总数。
样例输入
1
4 6
+---+---+---+---+---+---+
|---|---|---|---|---|---|
|***|***|** |** |** |***|
|---|---| * | * | * |---|
+---+---+---+---+---+---+
|---|---|---|---|---|---|
|---|** |** |***|** |** |
|---| * | * |---| * | * |
+---+---+---+---+---+---+
|---|---|---|---|---|---|
|***|** |***|***|***|** |
|---| * |---|---|---| * |
+---+---+---+---+---+---+
|---|---|---|---|---|---|
|** |---|***|---|** |** |
| * |---|---|---| * | * |
+---+---+---+---+---+---+样例输出
Number of solutions: 2分析
从题目描述中可以容易地得出判断，进入空白图案的木块后无法再向其他木块前进，因此是“死胡同”。很明显，也不能走到迷宫边界之外。进入包含横向图案的木块后只能沿着原有的方向继续前进，不能改变方向。进入带折线图案的木块后只能左转和右转。由于题目要求的是找出所有可能的不同路径，因此在迷宫的行进过程中需要记录已经走过的木块，在具体实现时，可以使用一个二维数组予以记录。对于进入木块后行进方向的改变，可以根据当前行进方向和木块所具有的图案进行判定。
在下述实现中，考虑了输入可能给出“旋转版本”图案的情况，并考虑了输入中可能包含空格的情况（尽管木块上的图案是可以旋转的，但UVa OJ上的评判数据似乎较弱，并未包含“旋转版本”的测试数据，所有评判数据均以初始给定的样式出现，题目中未完全明确地说明这一点而只是给出了暗示。uDebug上的测试数据给出了只包含一个单元格的迷宫，此种情况下，不论单元格内是否包含图案，不同路径数均为2。不过评判数据中似乎并未包含这样的测试数据）。因为从初始的左上角木块只能向右和向下走，因此不妨就假设左上角的木块图案包含的就是直线，不影响结果的正确性，以便于编码的实现。
参考代码
string line;
int m, n, maze[70][70], used[70][70], paths, cases;
int offset[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// d为方向：0表示向右, 1表示向下, 2表示向左, 3表示向上。
void dfs(int i, int j, int d)
{
if (i == m && j == n) { paths++; return; }
// 根据当前木块的图案和行进方向确定下一个到达的木块和后续行进方向。
used[i][j] = 1;
for (int next = 0; next <= 3; next++) {
if ((maze[i][j] == 1 || maze[i][j] == 3) && next > 0) continue;
if (maze[i][j] == 2 && (next == 0 || next == 2)) continue;
int nextd = (d + next) % 4;
int ii = i + offset[nextd][0], jj = j + offset[nextd][1];
if (ii >= 1 && ii <= m && jj >= 1 && jj <= n)
if (!used[ii][jj] && maze[ii][jj])
dfs(ii, jj, nextd);
}
used[i][j] = 0;
}
int main(int argc, char *argv[])
{
cin >> cases;
for (int c = 1; c <= cases; c++) {
// 读入迷宫。
cin >> m >> n; cin.ignore(1024, '\n');
memset(maze, 0, sizeof(maze));
for (int i = 1; i <= m; i++) {
getline(cin, line); getline(cin, line); getline(cin, line);
for (int j = 1, k = 0; j <= n; j++) {
while (line[k] != '|') k++;
for (k++; line[k] != '|'; k++)
if (line[k] == '*')
maze[i][j]++;
}
getline(cin, line);
}
getline(cin, line);
// 回溯并输出结果。
paths = 0, maze[1][1] = 3;
dfs(1, 1, 0); dfs(1, 1, 1);
cout << "Number of solutions: " << paths << '\n';
}
return 0;
}强化练习
258 Mirror MazeD，296 SafebreakerC，710 The GameD，11283 Playing BoggleC。
扩展练习
10501 Simplified Shisen-ShoE。
提示
对于10501 Simplified Shisen-Sho，截至2020年1月1日，此题的题目描述有两处文字错误：“As a side effect, this also means that ... in horizontal or diagonal”应为“As a side effect, this also means that ... in horizontal or vertical”；“Each tile in the board ... and (n,m) the lower left”应为“Each tile in the board ... and (n,m) the lower right”。由于此题的评测数据似乎较弱，不需使用剪枝技巧即可获得Accepted。
在完全搜索中，有一类题目并不需要显式地使用回溯来寻找解，而是可以通过多重循环的方式来构造出所有可能的解，在此过程中可能还需要进行额外的操作，例如考虑解中元素的顺序，或者需要使用剪枝技巧以缩短运行时间等。
强化练习
608 Counterfeit DollarA，735 Dart-a-ManiaB，10365 BlocksB，10660 Citizen Attention OfficesB，10662 The WeddingC。
扩展练习
1051 Bipartite NumbersE，10483 The Sum Equals the ProductD。
在回溯相关的题目中，如果问题空间较小且需要搜索全部问题空间获得最优解，可以应用库函数中的next_permutation来进行全排列的生成，将全排列映射到问题空间，从而可以通过检查某个排列是否为可行解。需要注意的是，使用该函数前需要将元素进行排序，使得元素为递增序，后续应用此函数才能生成所有的全排列，否则会漏掉一部分排列。
强化练习
102 Ecological Bin PackingA，418 MoleculesC，628 PasswordsA，725 DivisionA，921 A Word Puzzle in the Sunny MountainsE，11412 Dig the HolesD。
扩展练习
618 Doing WindowsD，1079 A Careful ApproachD。
提示
1079 A Careful Approach中，可以遍历所有可能的飞机降落顺序，对于每一种降落顺序，二分搜索最大可能的minimum achievable time gap。
在解题时，有时需要枚举给定大小为n的集合的所有子集，使用下述方法可以高效地列出大小为1～n的所有子集[12]。
//------------------------------1.2.1.cpp------------------------------//
// 输出子集所包含的元素。
void print(int flag[], int idx)
{
for (int i = 0; i < idx; i++)
cout << setw(2) << right << flag[i];
cout << '\n';
}
// 利用递归生成子集。
void generate(int flag[], int idx, int last, int n)
{
if (idx < last) {
if (idx == 0) {
for (int i = 0; i < n; i++) {
flag[idx] = i;
generate(flag, idx + 1, last, n);
}
}
else {
for (int i = flag[idx - 1] + 1; i < n; i++) {
flag[idx] = i;
generate(flag, idx + 1, last, n);
}
}
}
else print(flag, idx);
}
// 逐个枚举大小1～n的子集。
void enumeratingSubset(int n)
{
for (int i = 1; i <= n; i++) {
int *flag = new int[n];
generate(flag, 0, i, n);
delete [] flag;
}
}
//------------------------------1.2.1.cpp------------------------------//强化练习
471 Magic NumbersB，574 Sum It UpA，598 Bundling NewspapersC，947 Master Mind HelperD。
有些题目要求的并不是所有排列而是满足一定条件的全排列的子集，在这种情况下，可以通过回溯来生成所有子集，然后再对生成的子集应用题目所给定的约束条件进行检查。在很多时候，题目给定的限制是选择或不选择某个事物、经过或不经过某个位置等，可以应用二进制“位”来表示选择，用“位运算”来对限制进行模拟。
强化练习
124 Following OrdersA，648 StampsD，872 OrderingB，10475 Help the LeadersD，10776 Determine The CombinationB。
扩展练习
549 Evaluating an Equations BoardE，10858 Unique FactorizationC。
单向搜索是从起始状态开始向着终止状态（或者相反，从终止状态开始向着初始状态）不断进行搜索，搜索“路径”是一条“单行道”。但对于某些搜索空间较大的题目，仅使用单向搜索可能容易超时，此时同时从起始状态和终止状态开始相向进行搜索可以减小搜索空间，更快地得到解，这样的搜索方法称之为双向搜索，又称为“中间相遇搜索”（meet in middle search）。
给定n个等长的段落，编号为1～n。现在要求将其按照1, 2, …, n的顺序排列。利用剪贴板，你可以使用快捷键复制（Ctrl+X）和粘贴（Ctrl+V）轻松地实现。在此过程中，要求在粘贴前不能剪切两次，但是可以一次性剪切多个相邻段落，然后粘贴到其他地方。当然，段落在粘贴时和被剪切时的顺序一致。
例如，为了将段落{2, 4, 1, 5, 3, 6}调整为有序，你可以剪切段落1并将其粘贴在段落2前，然后剪切段落3并将其粘贴在段落4前。又例如，对于段落{3, 4, 5, 1, 2}，一次复制和粘贴就能够将此段落序列恢复为有序，总共有两种方式可以实现：一种是剪切{3, 4, 5}并将其粘贴在{1, 2}之后，或者剪切{1, 2}并将其粘贴在段落{3, 4, 5}之前。
输入
输入包含至多20组测试数据，每组测试数据包括两行输入数据，第1行包含一个整数n，表示段落的数量，第2行包含序列1, 2, 3, …, n的一个排列，表示段落的当前状态。最后一组测试数据后面紧跟一个0，此行数据不需处理。
输出
对于每组测试数据，输出测试数据组数及使得段落恢复有序状态所需的最少剪切/粘贴操作次数。
样例输入
6
2 4 1 5 3 6
5
3 4 5 1 2
0样例输出
Case 1: 2
Case 2: 1分析
不难得出，对于任意一个长为n的段落序列，至多只需(n − 1)次剪切/粘贴操作即可将其恢复为有序状态：按照1到n − 1的顺序逐次将第i个段落剪切并粘贴到第(i + 1)个段落前即可。也就是说，对于n = 9的测试数据，最多只需8次操作即可完成操作。但是从初始状态出发，每一步可能需要尝试的剪切/粘贴组合达102数量级，如果使用单向搜索，则需要1016级别的计算量，在时间限制内显然不可接受。如果从初始状态1, 2, 3, …, n和给定状态分别开始搜索，则只需各搜索4步即可，则计算量为之前的一半，为108数量级，通过优化剪切/粘贴的模拟操作，可以在时间限制内获得解决方案。由于是求最少操作次数，使用BFS解题可以更快地得到解。本题的难点是如何快速地获取某个段落序列在一次操作之内所能获得的其他段落序列，如果此环节处理效率较低，容易导致超时。
扩展练习
707 RobberyD。
由于回溯是通过遍历所有的可能方案然后从中寻找可行解，当搜索空间很大时，对一些明显不可能得到可行解的搜索分支继续进行搜索，会浪费时间，降低搜索效率。如果能够越早发现这些不可能构成可行解的搜索分支并将之“剪除”，则可以节省搜索时间，从而提高效率。
剪枝（prune）是对搜索分支进行剪除的形象类比，它类似于园丁对园木的“剪枝”——剪除已经死掉或不符合要求的枝叶——使得树的营养尽可能提供给需要的地方。在搜索中，剪枝将明显不可能得到解的搜索分支从搜索中去除，使得有限的CPU时间用在可能得到解的搜索分支上。但是剪枝并不是越多越好，因为剪枝本身也是需要代价的（某些剪枝需要消耗较多的CPU时间），如果花费较多的CPU时间进行某个剪枝，而剪枝得到的效益却不能超过所消耗的CPU时间，这样的剪枝将失去意义。
剪枝的具体做法需要根据具体问题而定，通常是根据题目所设的限制条件来进行，需要一些逻辑推理能力和想象力。一般来说，可以将剪枝分为两类，一类是可行性剪枝，另外一类是最优化剪枝。可行性剪枝是指在搜索过程中遇到不可能到达目标状态的分支予以剪除，例如在最长简单路径搜索过程中，如果顶点A和顶点B之间无通路，那么再去搜索A到B的路径显然是浪费时间。最优化剪枝是指当前选择的代价与最优选择代价相比已经不具有优势，那么很显然，可以不必对此搜索分支继续进行搜索。
古人有云：“熟读唐诗三百首，不会吟诗也会吟。”剪枝水平需要通过多做练习来提升。研习他人的剪枝思路也有助于增强自身思维能力。以下通过对若干题目进行的解析，以期读者能够对剪枝的一般思路和方法有一个较为直观的印象。
Geroge将同样长度的木棒随机切断，直到所有木棒的长度均不大于50单位长度。现在他想把木棒还原成原来的状态，但是他忘记了原来有多少根木棒，也忘记了原来每根木棒的长度是多少。请帮助Geroge设计一个程序，确定木棒最小的可能长度。所有给出的木棒长度均为大于0的整数。
输入
输入包含多组测试数据。每组测试数据由两行组成，第1行为一个整数，表示在切割后木棒的数量；第2行包含各木棒的长度数据，以空格分隔。输入的最后一行包含一个整数0。
输出
对于输入中的每组数据，输出原来木棒最小的可能长度。
样例输入
9
5 2 1 5 2 1 5 2 1
0样例输出
6分析
基本思路是先预设一个长度，然后通过尝试选取木棒进行拼接验证的方式来确定该长度是否可行。在拼接时需要考虑所有可能的拼接组合。由于搜索空间很大，单纯使用回溯无法在规定的时间限制内得到答案，必须进行剪枝。剪枝可以通过以下几个方面来进行。
（1）由于木棒的原始数量和长度均为整数，给定一组数据后，该组数据中木棒的初始长度不能是任意的。设初始时木棒长度为L，切割后所有木棒的长度和为S，则L的可能值有一个范围，最小为切割后现有木棒长度的最大值，最大为S，且L必须能够整除S。
（2）将木棒按切割后的长度从大到小的顺序进行取用，有利于减少回溯时的递归层数。
（3）若第i根木棒和第(i − 1)根木棒长度相同，且第(i − 1)根木棒未能被成功使用，则第i根木棒肯定也不会被使用。如果先前的拼接是正确的，则第(i − 1)根木棒应该会被使用，没有使用是因为不能构成满足要求的木棒而剩余，那么同样长度的第i根木棒在后续过程中肯定也不会被使用，表明不必在此搜索分支上继续搜索。
（4）在每次选取木棒时，当前已经拼接的长度加上选取的第i根木棒后，应该不大于预设的长度L，否则无法拼接出满足要求的木棒；第i根木棒开始的后续所有木棒长度之和加上已经拼接的长度必须不小于预设长度L，否则即使用完后续的所有木棒也得不到长度为L的木棒。
以下的代码中，在进行拼接验证时，拼接的子目标是逐次完成一段目标长度的木棒，当完成一段后，继续拼接下一段，直到拼接完成的木棒数达到预设数量或中途无法完成拼接而退回到上一层回溯。
参考代码
// stick[i]存储切割后第i根木棒的长度；
// remain[i]存储从第i根木棒开始后续所有木棒的长度和；
// used[i]表示第i根木棒是否已经被使用；
// goal表示每次预设的原始木棒长度；
// total表示原始木棒的数量；
// n为切割后木棒的数量。
int stick[105], remain[105], used[105], goal, total, n;
// 使用回溯法对预设的木棒原始长度进行拼接验证。
// idx表示可用木棒的搜索起始序号；
// done表示当前段木棒拼接是否完成；
// sum表示当前段木棒已经拼接的长度；
// cnt表示已经得到的原始长度的木棒数量。
bool dfs(int idx, int done, int sum, int cnt)
{
// 检查当前段木棒是否拼接完毕。
if (sum == goal) {
// 检查是否已经完成所有拼接。
if (cnt + 1 == total) return true;
if (dfs(0, 1, 0, cnt + 1)) return true;
return false;
}
// 当前段木棒拼接完成，选取尚未被使用的木棒继续下一段目标长度木棒的拼接。
if (done == 1) {
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = 1;
if (dfs(i + 1, 0, stick[i], cnt)) return true;
used[i] = 0;
break;
}
} else {
// 当前段木棒拼接尚未完成，继续选取可用的木棒完成。idx限制了可用木棒的起始序号。
for (int i = idx; i < n; i++)
// 剪枝：已拼接的长度加上当前木棒长度不能大于目标值；加上后续所有木棒长度不能
// 小于目标值（否则使用剩余的所有木棒也无法完成拼接）。
if (!used[i] && sum + stick[i] <= goal && sum + remain[i] >= goal) {
// 剪枝：当前木棒和上一木棒长度相同且上一木棒未使用，那么使用当前木棒肯定
// 也不可能完成拼接。
if (i && stick[i] == stick[i - 1] && !used[i - 1]) continue;
// 尝试使用当前木棒。
used[i] = 1;
if (dfs(i + 1, 0, sum + stick[i], cnt)) return true;
used[i] = 0;
// 剪枝：某次拼接已经达到了预设长度，但是未能成功返回，说明预设长度不正确，
// 不必再继续尝试进行拼接。
if (sum + stick[i] == goal) return false;
}
}
return false;
}
int main(int argc, char *argv[])
{
while (cin >> n, n) {
// 读入数据，统计所有木棒的长度和。
int length = 0;
for (int i = 0; i < n; i++) {
cin >> stick[i];
length += stick[i];
}
// 将切割后的木棒长度按照从大到小的顺序进行排列。
sort(stick, stick + n, greater<int>());
// 计算从第i根木棒开始的后续木棒长度和，为可行性剪枝做准备。
remain[n] = 0;
for (int i = n - 1; i >= 0; i--) remain[i] = remain[i + 1] + stick[i];
// 从小到大遍历可能的木棒初始长度，回溯进行拼接验证。
for (goal = stick[0]; goal <= length; goal++) {
// 确定木棒的初始长度和木棒的原始数量。
if (length % goal) continue;
total = length / goal;
// 进行拼接验证，成功则输出。
memset(used, 0, sizeof(used));
if (dfs(0, 1, 0, 0)) {
cout << goal << '\n';
break;
}
}
}
return 0;
}强化练习
228 Resource AllocationE，269 Counting PatternsE，301 TransportationB，437 The Tower of BabylonA，519 Puzzle (II)D，624 CDA。
扩展练习
219 Department of Redundancy DepartmentE。
受哈尔滨冰雕的启发，来自北极机器人与自动机大学（Arctic University of Robotics and Automata）的参赛队员决定程序竞赛结束后在校园内举办自己的冰雪节。他们打算在冬天结冰的时候，从学校附近的一个湖里获取冰块。为了便于监测湖中冰层的厚度，他们先将湖面网格化，然后安置一个轻巧的机器人逐个方格测量冰层的厚度。在网格中有3个特殊方格被指定为“检查点”，对应着机器人在检查过程中经过整个行程的四分之一、二分之一、四分之三的位置，机器人在这3个特殊“检查点”会发送相应的进度报告。为了避免对冰面造成不必要的磨损和划痕而影响后续的使用，机器人需要从网格左下角坐标为(0, 0)的方格出发，经过所有方格仅且一次，然后返回位于坐标为(0, 1)的方格。如果有多种路线符合要求，则机器人每天会使用一条不同的路线。机器人只能沿北、南、东、西4个方向每次移动一个方格。
给定网格的大小和3个检查点的位置，编写程序确定有多少种不同的检查路线。例如，湖面被划分为3 × 6的网格，3个检查点按访问的顺序分别为(2, 1)、(2, 4)和(0, 4)，机器人必须从(0, 0)方格开始，路经18个方格，最后终止于(0, 1)方格。机器人必须在第4（即
）步的时候经过(2，1)方格，在第9（即
）步的时候经过(2, 4)方格，第13（即
）步的时候经过(0，4)方格，只有两种路线符合要求，如图1-11所示。
图1-11 符合要求的两种路线
需要注意：（1）当网格的大小不是4的倍数时，在计算步数时使用整除；（2）某些情况下可能不存在符合要求的路线，例如给定一个4 × 3的网格，3个检查点分别为(2, 0)、(3, 2)和(0, 2)，那么将不存在从(0，0)方格出发，结束于(0, 1)方格且满足要求的路线。
输入
输入包含多组测试数据。每组测试数据的第1行包含两个整数m和n，
，
，表示网格的行数和列数，接着的一行包含6个整数
，
，
，
，
，
，其中
，
，i = 1，2，3。输入的最后一行包含两个0。
输出
从1开始输出测试数据的组数，输出以下不同路线的数量：机器人从行0列0出发，在行0列1结束，在第
步时经过行
和列
，i = 1，2，3，能够路经所有方格仅且一次的路线。输出格式参照样例输出。
样例输出
3 6
2 1 2 4 0 4
4 3
2 0 3 2 0 2
0 0样例输出
Case 1: 2
Case 2: 0分析
本题要求使用完全搜索来得到所有可能的路线，从图论角度看，等价于求隐式图中所有可能的哈密顿回路[3]，如果不加以剪枝，难以在限定时间内获得通过。根据题目约束，令机器人当前所在行为r，列为c，已经行进的步数为moves，used[i][j] = 0表示该方格尚未访问，used[i][j] = 1表示该方格已经访问，可以进行以下的剪枝来选择下一步移动的候选方格。
（1）进入该方格后，如果r＜0或
或c＜0或
，表明机器人已经位于网格之外，则该方格不能作为候选方格；
（2）机器人进入的方格状态used[i][j] = 1，即方格已经访问，则该方格不能作为候选方格；
（3）如果进入的方格坐标为(0, 1)，但行进步数不等于m × n，则表明提前到达了达终止方格(0, 1)，那么该方格不能作为候选方格；
（4）当前行走步数moves达到某个检查点所对应的步数时，但所处方格不是对应的检查点，那么此方格不能作为候选方格；
（5）如果当前方格是特定的检查点，但对应的步数moves与要求的步数不相符合，那么此方格不能作为候选方格；
（6）如果从当前方格到达下一个检查点所需要的最少步数（最少步数可通过两个方格坐标分量的差值的绝对值之和得到）与当前已经行走的步数moves之和大于下一个检查点所要求的步数，那么此方格不能作为候选方格；
（7）如果访问某个方格后，导致剩余尚未访问的方格不连通，则这些方格不能作为候选方格。可以通过从终止方格(0, 1)进行一次DFS来确定尚未访问方格的连通性。
使用上述剪枝技巧已经能够在限定时间内获得Accepted。为了提高搜索效率，还可以对候选方格再进行进一步的优化和剪枝。首先进行统计，对于当前所在方格的候选方格，统计候选方格的“可选邻近方格”（即到达此候选方格后可以选择前进方格）的数目。
根据“可选邻近方格”数量为1的候选方格的数目来确定下一步的行走方向。
（1）如果“可选邻近方格”的数量为1的候选方格有多个，表明一旦进入这些候选方格，将无法继续访问其他方格，因此不能进入这些候选方格中的任意一个；
（2）如果“可选邻近方格”的数量等于1的候选方格只有一个，那么应该选择此候选方格，因为需要访问所有方格仅且一次；
（3）如果“可选邻近方格”的数量为1的候选方格不存在，则表明进入候选方格中的任意一个之后，均有至少两种方向可供选择行走，因此轮流选择上、下、左、右4个可行的候选方格之一进行回溯。
例如，如图1-12所示，深色方格为已访问方格，浅色方格为未访问方格，当前行走到标记了“*”号的方格，接下来可以选择进入1号方格或者5号方格。与1号方格相邻的为2号、3号、4号方格，其中2号和3号方格的“可选邻近方格”数量均为1，4号方格的“可选邻近方格”数量为3，按照剪枝技巧，不应选择1号方格作为下一步行走的候选方格。对于5号方格来说，与其相邻的有4号和6号方格，其中4号方格的“可选邻近方格”数量为3，6号方格的“可选邻近方格”数量为1，满足剪枝技巧的条件，因此应该优先选择5号方格作为下一步行走的方格。
图1-12 根据“可选邻近方格”数量确定行走方向
更进一步地，由于前述的搜索方法采用的是单向搜索的方式，还可以运用双向搜索以减少递归深度从而提高搜索效率，不过这样编码的难度较高，不易实现。
参考代码
int m, n, cnt, used[8][8], T;
int offset[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int checkIn[4][2], checkMove[4], visited[8][8];
int dfs(int r, int c)
{
if (r < 0 || r >= m || c < 0 || c >= n) return 0;
if (visited[r][c] || used[r][c]) return 0;
visited[r][c] = 1;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
}
inline bool go(int r, int c, int moves, int spots)
{
// 范围检查。
if (r < 0 || r >= m || c < 0 || c >= n) return false;
// 进入的方格未被使用。
if (used[r][c]) return false;
// 检测当坐标到达检查点时，步数是否符合要求。
if (r == checkIn[spots][0] && c == checkIn[spots][1])
if (moves != checkMove[spots])
return false;
// 检测步数达到检查点的步数时，坐标是否符合要求。
if (moves == checkMove[spots])
if (r != checkIn[spots][0] || c != checkIn[spots][1])
return false;
// 检测到达下一个检查点所需最少步数是否符合要求。
int needed = abs(r - checkIn[spots][0]) + abs(c - checkIn[spots][1]);
if (moves + needed > checkMove[spots])
return false;
// DFS确定未访问的方格的连通性。
used[r][c] = 1;
memset(visited, 0, sizeof(visited));
int unused = dfs(0, 1);
used[r][c] = 0;
if (unused != (T - moves))
return false;
// 检查是否到达终止方格。
if (r == 0 && c == 1)
if (moves != T)
return false;
// 符合要求的候选方格。
return true;
}
void backtrack(int r, int c, int moves, int spots)
{
if (moves == T) { cnt++; return; }
if (r == checkIn[spots][0] && c == checkIn[spots][1]) spots++;
int rr, cc;
for (int k = 0; k < 4; k++) {
rr = r + offset[k][0], cc = c + offset[k][1];
if (go(rr, cc, moves + 1, spots)) {
used[rr][cc] = 1;
backtrack(rr, cc, moves + 1, spots);
used[rr][cc] = 0;
}
}
}
int main(int argc, char *argv[])
{
int cases = 0;
checkIn[3][0] = 0, checkIn[3][1] = 1;
while (cin >> m >> n) {
if (m == 0) break;
for (int i = 0; i < 3; i++) {
cin >> checkIn[i][0] >> checkIn[i][1];
checkMove[i] = (i + 1) * m * n / 4;
}
T = m * n, checkMove[3] = m * n;
memset(used, cnt = 0, sizeof(used));
used[0][0] = 1;
backtrack(0, 0, 1, 0);
cout << "Case " << ++cases << ": " << cnt << '\n';
}
return 0;
}给定一组长度不等的木棍，你能够将其首尾相连使之构成一个正方形吗？
输入
输入第1行包含整数N，表示测试数据的组数。每组测试数据由一行构成，起始为一个整数
)，表示木棍的数量，接着是M个整数，表示每根木棍的长度，长度为1～10000之间的某个整数。
输出
对于每组测试数据，输出一行。如果可以将所有木棍拼接成一个正方形，输出yes，否则输出no。
样例输入
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5样例输出
yes
no
yes分析
由于本题的测试数据规模较大，即使采取较为高效的剪枝技巧，还是难以在时间限制内获得通过。观察题目的约束，题目只是要求判断给定的木棍是否可以构成正方形，那么在回溯过程中可以将已经回溯的状态予以保存，当某次回溯再次到达此状态时可以直接返回不可行，因为此回溯过程只要一次成功即可，既然在此前的回溯过程中到达了此状态，但是未能成功返回，则说明此状态的木棍拼接并不可行，因此提前结束回溯可以显著缩短搜索时间。题目给定最多只有20根木棒，则可以使用一个整数数组来表示木棒的使用状态，结合位运算技巧，可以快速进行状态的标记和查询，以便在回溯过程中获取下一根可用的木棒，此技巧和动态规划中使用的备忘技巧类似。
参考代码
int n, stick[22], size, ONES, marked[(1 << 20) + 10] = {};
bool dfs(int used, int depth, int side)
{
if (marked[used]) return false;
if (side == size) return dfs(used, depth + 1, 0);
if (depth == 4) return true;
marked[used] = 1;
int available = ONES & (~used), next, bit;
while (available) {
next = available & (~available + 1);
available ^= next;
bit = __builtin_ctz(next);
if (side + stick[bit] > size) continue;
if (bit && stick[bit] == stick[bit - 1] && !(used & (next >> 1))) continue;
if (dfs(used | next, depth, side + stick[bit])) return true;
}
return false;
}
int main(int argc, char *argv[])
{
int cases;
cin >> cases;
for (int cs = 1; cs <= cases; cs++) {
cin >> n;
int side = 0;
for (int i = 0; i < n; i++) {
cin >> stick[i];
side += stick[i];
}
if (side % 4 != 0) {
cout << "no\n";
continue;
}
size = side / 4;
sort(stick, stick + n, greater<int>());
if (stick[0] > size) {
cout << "no\n";
continue;
}
ONES = (1 << n) - 1;
memset(marked, 0, (1 << n) * sizeof(int));
cout << (dfs(0, 0, 0) ? "yes" : "no") << '\n';
}
return 0;
}强化练习
10164 Number GameD，10419 Sum-Up the PrimesD，10447 Sum-Up the Primes (II)E。
提示
10419 Sum-up the Primes题目约束条件较松，此题可通过单纯的回溯法解决，使用备忘技巧对减少运行时间效果不佳。可以将问题转化为子集和问题进而使用动态规划解决。
10447 Sum-up the Primes (II)的时间限制非常紧，需要进行适当地剪枝才能在时间限制内获得Accepted。一个可行的剪枝技巧是利用奇偶性，假设不能使用素因子2，则当给定的N为奇数但t为偶数，或者给定的N为偶数t为奇数，显然无解。类似于10419 Sum-up the Primes，可以将问题转化为子集和问题进而使用动态规划解决。
今天是我母亲的生日，我想为她制作一个生日蛋糕。蛋糕共有m层，每层都是一个圆柱体，整个蛋糕的体积恰好为nπ。从蛋糕的底部开始，各层蛋糕的序号依次为1, 2, …, m，构成第i层蛋糕的圆柱体底面半径为ri，高度为hi，两者均为正整数，为了使蛋糕看起来更为美观，要求各层蛋糕满足以下条件：对于任意i＜m，ri＞ri + 1，hi＞hi + 1。
整个蛋糕的表面都将被抹上冰淇淋，为了使蛋糕的制作成本稍微低一些，我们决定使用尽可能少的冰淇淋来实现这个目标。换句话说，蛋糕的表面积应该尽可能的小（蛋糕的最底面不计入表面积，因为该面不需要涂抹冰淇淋）。
输入
输入包含至多10组测试数据。每组测试数据包含两个整数n，m（n＜100001，m＜11），分别表示蛋糕的体积和总层数。最后一组测试数据后跟着一个0，该行不需处理。
输出
对于每组测试数据，输出测试数据的组数及一个整数S，表示蛋糕的最小表面积为Sπ。如果无法制作出符合要求的蛋糕，输出0。
样例输入
100 2
1000 3
0样例输出
Case 1: 68
Case 2: 316分析
如果单纯使用回溯不加剪枝，将难以在限制时间内获得通过。令r为圆柱体的底面半径，h为圆柱体的高，则其体积V = πr2h，侧面积S侧 = 2πrh，底面积S底 = πr2，表面积S表 = S侧 + 2S底，且体积和侧面积存在关系S侧 = 2V/r。
由于要求构成蛋糕的圆柱体从下层往上层半径和高均递减，则在回溯时考虑从大到小枚举圆柱体的半径和高。在回溯时定义以下参数：depth表示回溯的层次，即当前是为第几层蛋糕确定半径和高，从0开始计数，最底层的蛋糕对应第0层；volume表示当前蛋糕的总体积；surface表示当前蛋糕需要涂抹冰淇淋的总表面积，由题意不难推知，该表面积等价于构成蛋糕的各个圆柱体的侧面积加上最底层圆柱体的底面积；r表示当前层蛋糕的底面半径；h表示当前层蛋糕的高度；best表示满足体积为n层数为m的蛋糕的最小表面积。根据题目约束，可以在回溯过程中应用以下优化技巧以提高效率。
（1）当volume大于n或surface大于等于best时予以剪枝；
（2）当回溯层次大于0时，即确定第2层（或以上）蛋糕的底面半径和高时，根据体积和侧面积存在的关系S侧 = 2V/r，结合当前蛋糕的体积和目标体积的差，可以得到由剩余体积而导致至少还需要增加的表面积remain = 2 × (n − volume)/r，如果总的蛋糕表面积
时予以剪枝；
（3）根据剩余的体积n − volume及当前回溯的层次m可以得到当前层蛋糕的最大和最小可能底面半径；
（4）根据当前蛋糕的体积volume，当前层蛋糕的底面半径ri，后续每层蛋糕的最小可能高度m − depth，可以得到至少还需增加的体积V增 = ri2 × (m − depth)，若volume + V增＞n，可以略过在底面半径为ri时对当前层蛋糕高度hi的继续搜索；
（5）根据剩余的体积n − volume及当前回溯层数m、枚举的当前层蛋糕的底面半径ri可以确定当前层蛋糕的最大和最小可能高度；
（6）根据当前蛋糕的体积volume，枚举的当前层蛋糕的高度hi，后续每层蛋糕的最小可能底面半径m − depth，可以得到至少还需增加的体积V增 = (m − depth)2 × hi，若volume + V增＞n，不需进入下一层回溯；
（7）考虑当前层蛋糕对体积的贡献V增 = ri2 × hi，由剩余的体积可以估算至少还需增加的表面积remain = 2 × (n − volume − V增)/ri，如果总的蛋糕表面积
时予以剪枝；
（8）根据给定的初始蛋糕体积和层数，可以预估得到最小表面积best和初始的最大底面半径r及最大高度h。
值得一提的是，本题中对底面半径和高度的搜索方向显著影响了搜索效率，从大到小进行搜索比从小到大进行搜索明显要快得多。可能的原因是在枚举较大的底面半径时，缩小了高度的范围，从而更快地得到一个较优的最小表面积，进而能够剪除更多的搜索分支，最终带来效率的较大提升。
参考代码
int n, m, best;
void dfs(int depth, int volume, int surface, int r, int h)
{
// 优化技巧（1）。
if (volume > n || surface >= best) return;
// 回溯层次达到要求，检查体积是否满足条件，若满足更新最小表面积。
if (depth == m) {
if (volume == n) best = min(best, surface);
return;
}
// 优化技巧（2）。
if (depth) {
int remain = (n - volume) * 2 / r;
if (surface + remain >= best) return;
}
// 优化技巧（3）。
int maxr = sqrt(1.0 * (n - volume) / (m - depth));
for (int ri = min(maxr, r); ri >= (m - depth); ri--) {
// 优化技巧（4）。
if (volume + ri * ri * (m - depth) > n) continue;
// 优化技巧（5）。
int maxh = (n - volume) / (ri * ri);
for (int hi = min(maxh, h); hi >= (m - depth); hi--) {
// 优化技巧（6）。
if (volume + (m - depth) * (m - depth) * hi > n) continue;
int volumeDiff = ri * ri * hi, areaDiff = 2 * ri * hi;
if (!depth) areaDiff += ri * ri;
// 优化技巧（7）。
int remain = (n - volume - volumeDiff) * 2 / ri;
if (surface + remain >= best) break;
dfs(depth + 1, volume + volumeDiff, surface + areaDiff, ri - 1, hi - 1);
}
}
}
int main(int argc, char *argv[])
{
int cases = 0;
while (cin >> n) {
if (n == 0) break;
cin >> m;
// 优化技巧（8）。
best = 4 * n;
dfs(0, 0, 0, sqrt(n), n);
if (best == (4 * n)) best = 0;
cout << "Case " << ++cases << ": " << best << '\n';
}
return 0;
}强化练习
222 Budget TravelB，525 Milk Bottle DataE，560 MagicD，1217 Route PlanningE，10890 MazeD，11127 Triple-Free Binary StringsD。
扩展练习
229 ScannerD，835 Square of PrimesD，11199 Equations in DisguiseE。
提示
10890 Maze的题目描述中未明确说明进入某个包含宝物的方格是否必须要将其拾取，按照Accepted代码的预设，不需要一定将其拾取，而是可以忽略所经路径的某件宝物。
对于835 Square of Primes，如果不考虑顺序，使用回溯法进行搜索很容易超时。根据题意，最后一行和最后一列的素数必定是数位全部为奇数的素数，则当给定和为偶数时，必定无解。在10000～99999中，共有8363个素数，而其中全部数位均为奇数的素数共有608个。因此，按照如下策略来设置搜索顺序可以显著提高搜索效率：预先生成具有指定和且首位数字为给定数字的所有素数，先确定主对角线上的素数，之后枚举位于最后一列和最后一行的素数，接着再确定倒数第2列的素数，之后再确定第1行～第4行的素数，在确定第1行～第4行的素数时，之前的素数已经确定了至少两个数位（第1行～第3行已经确定了3个数位），因此搜索范围可以进一步缩小。最后只需进行第1列～第3列和副对角线的素数检测，如果通过，则为符合题意的一种素数方阵。
完美正方形剖分（perfect square dissection）是指给定一个边长为n的正方形，确定能否将其剖分为若干大小各异的小正方形，使得这些小正方形能够拼接得到原始的正方形。如果放宽问题的限制，剖分得到的小正方形不要求大小各异，则可以得到以下问题。
Tomy有许多正方形纸片，边长处于1～N − 1不等。实际上，每种边长的正方形他都有无数张。他曾经以拥有这些正方形而自豪，但是某一天，他突然想要得到一个更大的正方形——边长为N的正方形。虽然他手头上并没有这样的正方形，但是他可以通过将边长更小的正方形纸片拼接起来的以得到想要的正方形。例如，一个边长为7的正方形，可以由9个更小的正方形组成，如图1-13所示。
图1-13 9个小正方形组成边长为7的正方形
注意，在拼接过程中，不能留下空白区域，也不能将纸片放置在正方形的范围之外，而且纸片也不能互相重叠。正如你所猜想的，Tomy希望使用的纸片张数尽可能地少，你能帮助他完成这个任务吗？
输入
输入第1行包含一个单独的整数T，表示测试数据的组数。每组测试数据为一个单独的整数
。
输出
对于每组测试数据，输出一行，包含一个整数K，表示最少需要的纸片数。接下来K行，每行3个整数x，y，l，表示纸片左上角的坐标（ 
，
）以及纸片的边长。
样例输入
1
3样例输出
4
1 1 2
1 3 2
3 1 2
3 3 2分析
令需要拼接的正方形边长为N，根据题意易知，拼接方案是若干平方数之和。那么问题转化为如何将N表示为若干平方数之和且平方数的个数最小，这可以通过回溯法解决。但是，得到了一个将N拆分为平方数之和的方案，并不表示就能将这些大小的纸片拼接成边长为N的正方形。例如，对于N = 5，可以拆分为9与16的和，虽然9和16都是平方数，但是实际上无法将一张边长为3和一张边长为4的纸片拼接为边长为5的正方形。所以，在生成一个平方数和方案后，需要进行验证放置，若能放置，则表明此方案可行，予以记录，将所有可行的方案记录后，挑选其中纸片数最小的方案即为所求。这样的话，将N拆分为平方数之和是一层回溯，将拆分方案尝试放置又是一层回溯，需要通过两层回溯来解决本问题。
考虑到需要两层回溯来搜索可能的解决方案，如果不进行充分剪枝，在限定的时间内无法获得通过。在将N拆分为平方数之和的这一环节，如果能够得到一个拆分方案（尽管不是最优的，但是它的总个数较小且能实际放置），将此方案中平方数的个数作为阈值可“剪除”很多无效的搜索分支。可以按照以下方法构造一个符合上述要求的非最优方案：左上角放置一张边长为(N − 2)的纸片，然后在右侧和下方尽可能多地放置边长为2的纸片，剩余的空间放置边长为1的纸片，这样总的纸片数
，Nthreshold与N接近，可以做为一个较好的剪枝阈值。通过回溯发现了总个数更少的“平方数之和”方案后，则开始尝试实际放置：建立一个网格（可以使用二维数组表示），当填充边长为A的纸片时，在网格中查找是否有起始坐标为(x, y)且边长为A的空白区域，若无此类空白区域，表明该方案无法实际放置；若能找到，则枚举所有这样的起始位置，逐一进行放置。在尝试某位置后，需要将该区域标记为已填充，若后继填充不成功返回时则撤销标记。对于已经生成但不能实际拼接的拆分方案需要予以记录，在后继生成的方案中，若有方案与记录的方案相同，则直接忽略，不必再次浪费时间进行搜索。
当N mod 2 = 0或N mod 6 = 3时，有特殊的解法。当N mod 2 = 0时（即N为偶数），拼接方法为：用4张边长为N/2的纸片拼接得到边长为N的正方形。当N mod 6 = 3时，放置方法与N = 3的方案类似，只不过将相应的纸片边长增加同样的数量。与此同时，平方数25的拼接方案和5的拼接方案类似，49的拼接方案和7的拼接方案类似，则对于2～50的数，只需要求出素数的拼接方法即可。万维网上已经有2～50的素数的拼接方案和最少需要纸片数，如果只是为了解题，利用这些信息能够显著减少计算时间，也可以生成拼接方案后再提交。
关灯问题（lights out puzzle）的形式如下：给定R × C的网格，其中
，
，网格上每个方格内包含一盏电灯，当按下某个方格内电灯的开关时，会将此方格及其上下左右4个方格内的电灯亮灭状态反转，亦即原先点亮的灯会熄灭，原先熄灭的灯会点亮。假定按下某个方格内的电灯开关一次为一个步骤，给定初始的电灯亮灭状态（有的方格内电灯是亮的，有的方格内电灯是灭的），请确定是否可通过若干步骤将所有电灯熄灭，如果可以则确定所需要的最少步骤数。如图1-14所示，这是一个8 × 8的网格中电灯的初始亮灭状态。
图1-14 初始电灯状态，点亮的电灯为白色，熄灭的电灯为黑色
分析
将网格视为一个矩阵，亮的灯对应矩阵中为1的元素，灭的灯对应矩阵中为0的元素，则图1-14所示的初始状态可以使用一个矩阵表示。
按下网格内位于(i, j)的电灯开关等价于将初始状态矩阵L与一个“反转矩阵”Aij相加。其中“反转矩阵”Aij定义为一个3 × 3的矩阵，此矩阵中只有按下的位置及上下左右4个位置为1，其他位置为0，如果上下左右的4个位置位于边界之外则不予考虑。例如，A11对应于在网格(1，1)按下电灯开关时所对应的“反转矩阵”，同理可以推出A12和A22的含义。
由于矩阵的加法满足交换律，即各个矩阵相加的顺序和最终结果无关，因此可以将按下电灯的操作表示为一个线性代数方程。由于电灯的状态在反转两次后会恢复成原始的状态，因此上述线性方程可以视为模2状态下的线性方程组，有
使用高斯消元法在模2的情况下求解此线性方程组即可得到需要按下的电灯开关，计数为1的变量数量即为最少的操作步骤数。该方法的时间复杂度为O(R3C3)。
可以证明，对于R = C的情形，总是存在步骤数最少的唯一解。由于按下某个电灯开关时，反转的是一个“十字形”范围内电灯的状态，也就是说，在第i行第j列按下电灯，至多能使第(i − 1)行第j列的电灯状态发生反转，而对第(i − 1)行以前的电灯状态不可能产生影响。同时考虑到当R = C时必定存在解，而且按下开关的先后顺序对最后结果不产生影响，因此可以先枚举第 1 行电灯的按下状态，由此逐步确定后续行电灯是否按下。也就是说，如果在预先确定了第1行电灯的按下状态后，当回溯到第2行的第j列，如果此时第1行的第j列电灯仍然是亮的，那么就只能通过按下第2行第j列的电灯开关来使得第1行的第j列的电灯变成熄灭状态，对于后续行的每一列，都可以根据上一行对应列电灯的状态来确定此列的电灯是否需要按下。换句话说，第1行电灯的按下状态决定了后续行所有电灯是否按下的状态。那么可以使用回溯法枚举第1行电灯按下与否的所有情形，之后根据第1行的电灯亮灭状态推导后续行电灯是否按下即可。
需要注意，如果按下电灯开关后对周围方格的影响不是一个“十字形”，而是其他不规则的模式，则关灯问题不一定存在可行解，此时需要通过回溯搜索所有可能的解来确定。当n较大时，还需要使用剪枝技巧才能在限定时间获得通过。一个有效的剪枝技巧是当回溯到第3行或第3行以后，若第1行仍有未熄灭的电灯，则此回溯分支可以剪除，因为后续已经无法通过按下某个电灯按钮来使得第1行的电灯状态发生反转。
强化练习
10309 Turn the Lights OffC，10318 Security PanelC，11464 Even ParityC。
15数码问题是一个很流行的游戏，即使你没有听说过这个名字，你也一定见过。它由15个滑块构成，每个滑块标记有1～15的数字，所有滑块被放置在一个边长为4的正方形外框中，留有一个空位。游戏的目标是移动滑块使得它们最终排列成如图1-15所示的形式。
图1-15 目标排列方式
唯一符合规则的移动方式是将空位旁的若干滑块中的一个移动到空位，考虑如图1-16所示的一组移动。
图1-16 （从左至右依次为）起始布局，空位右移（R），空位上移（U），空位左移（L）。注意是空位移动而不是滑块移动
我们用与空位交换的邻位滑块来表示移动方式。可能的值为R, L, U, D，分别表示空位向右、左、上、下移动。
给出一个15数码问题的初始布局，找出一种移动方法使其转化为目标布局。测试数据中有解的问题均可以在不超过45步内解决，你的解最多只能用50步。
输入
输入的第1行包含一个整数N，表示测试数据的组数。接下来共4N行输入描述了N个问题，每4行描述一个。其中0表示空位。
输出
对于每组输入数据输出一行。如果给定的初始状态无解，输出This puzzle is not solvable.。如果有解，输出一个可行序列来描述操作过程。
样例输入
2
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14样例输出
LLLDRDRDR
This puzzle is not solvable.分析
定义单个滑块的n值为：按行优先顺序，在当前滑块之后出现并小于当前滑块数字的滑块数量。给定某种布局，可以使用下述方法来判断是否有解：令e表示空滑块所在的行序号（从1开始计数），统计各滑块的n值总和为
如果N + e为偶数，则当前布局有解，否则无解。例如，给定以下初始布局：
按照行优先顺序，在13号滑块之后出现且滑块数字小于13的滑块数量为12（滑块数字依次为10、11、6、5、7、4、8、1、12、9、3、2），在10号滑块之后出现且滑块数字小于10的滑块数量为9（滑块数字依次为6、5、7、4、8、1、9、3、2）……类似地，可以得到其他滑块的n值分别为（方括号内为滑块的数值，方括号之前为滑块的n值）：9[11]，5[6]，4[5]，4[7]，3[4]，3[8]，0[1]，3[12]，3[14]，2[9]，1[3]，1[15]，0[2]。所有滑块的n值之和N = 59，空滑块在第4行，即e = 4，则N + e = 63，为奇数，故以上布局不可解。
// 判断给定的布局是否可解。
bool solvable(vector<int> tiles)
{
int sum = 0;
for (int i = 0; i < tiles.size(); i++) {
if (tiles[i] == 0) sum += (i / 4 + 1);
else {
for (int j = i + 1; j < tiles.size(); j++)
if (tiles[j] && tiles[j] < tiles[i])
sum++;
}
}
return (sum % 2 == 0);
}由于空滑块至少可向两个方向移动，每增加一步，产生的布局数量以指数形式增长，不同的布局数量可能有16! = 20922789888000种，远远超过穷尽搜索在限制时间内所能解决的数据规模。对于此类搜索类型题目，可以使用以下几种方法尝试解决。
深度优先搜索（Depth First Search，DFS）[4]不断地向前寻找可行状态，试图一次找到通向目标状态的路径，它不会重复访问一个状态。由于某些问题所对应的搜索树包含大量的状态，一般来说，DFS只有在最大搜索深度固定的情况下才具有实用性。DFS维护一个栈，保存未访问过的状态，在每次迭代时，DFS从栈中弹出一个未访问的状态，然后从这个状态开始扩展，根据规定的走法计算其后继状态。如果达到了目标状态，那么搜索终止，否则，任何在闭合集中的后继状态都会被忽略，其他的未访问状态被压入栈中，继续搜索。使用DFS解题的过程可以使用伪代码描述如下[13]。
// initial为初始状态，goal为目标状态。
dfs (initial, goal)
{
// 如果初始状态即为目标状态，不需继续搜索。
if (initial = goal) return "Solution"
// 将初始状态的深度置为0。
initial.depth = 0
// 设置开放集，开放集表示尚未访问的状态。此处使用栈来存储开放集。
open = new Stack
// 设置闭合集，闭合集表示已经访问的状态。
closed = new Set
// 当开放集不为空且尚未找到符合要求的方案时继续搜索。
while (open is not empty)
{
// 从开放集中取出尚未访问的某个状态n。
n = pop(open)
// 将状态n送入闭合集中。
insert(closed, n)
// 根据游戏规则，检查状态n的所有可行后继操作m。
foreach valid move m at n
{
// 在状态n上执行操作m以获得某个后继状态next。
next = state when playing m at n
// 若闭合集中不包含状态next，则表明该状态尚未访问，其深度增加1。
// 检查状态next是否已经为目标状态goal，若为目标状态则返回解决方案。
// 若不为目标状态且深度小于预设深度限制则将其置入开放集等待继续搜索。
if (closed doesn't contain next)
{
next.depth = n.depth + 1
if (next = goal) return "Solution"
if (next.depth < maxDepth) insert(open, next)
}
}
}
// 若在限制深度内未发现解决方案则返回无解。
return "No Solution"
}需要注意，上述伪代码通过栈来实现DFS，与使用递归实现的DFS稍有差异。使用递归实现的DFS，在每个深度层次一般只保存一个状态，而此处使用栈实现的DFS，在每个深度层次会生成当前状态“紧随其后下一步”的多个状态并压入栈中，相对于使用递归实现的DFS栈状态，栈中同层次的状态可能不止一个。
DFS属于盲目搜索，在此过程中，大部分时间都用于在闭合集中搜索某个状态是否存在，如何快速地确定某个状态是否已经访问是提升算法效率的关键。如果能够为布局生成一个唯一键值，通过键值来判定两个布局的不同则相对方便得多。也就是说，如果两个布局有着相同的键值则表示两个布局是等价的，若两个布局拥有不同的键值，则其必定不同，这样就能够通过检索键值是否存在来确定布局是否已经访问。观察滑块所处的正方形外框，共有16个位置，最大滑块数字为15，不妨将布局视为16进制的数制系统，每个滑块作为一个数位，按行优先顺序将布局表示成一个unsigned long long int类型的整数。以前述的示例布局为例，可以将其唯一表示成：
通过此种方式，可以将布局唯一映射到一个整数，便于使用set数据结构来查询局面是否已经在闭合集合中。更进一步地，如果将布局对应的整数表示为二进制数形式，则每4个二进制位恰好表示一个滑块，后继移动空滑块的操作可以转换为位操作，这样可以减少状态表示所占用的空间，同时使用位操作也可以提高代码效率。
因为事先无法确定某个布局所对应解的长度，如果初始时的深度限制较小，当实际解的长度大于深度限制时，会出现DFS无法获得解的情形，其原因是DFS在达到解的深度之前就已经停止了搜索。对于本题来说，可能出现如下“诡异”的情形：某个布局距离目标布局只差几步，但由于达到了最大搜索深度限制而被放到了闭合集中，那么后续不可能再次对此布局进行扩展，即使之后的DFS过程在较小的深度等级访问到这个布局，它也不会继续搜索，因为这个布局已经在闭合集中。反过来，如果限制深度过大，则DFS会在某些无解的搜索分支上耗费大量时间，导致搜索时间大幅增加。因此，搜索深度设置是否合理直接影响着能否获得解和获得解所需要的时间。一般来说，对于可以使用DFS解题的题目，其搜索深度都有一定限制（或者题目本身所蕴含的搜索树深度不大，不需在题目描述中予以明确限定）。由于本题已经限定有解布局均可在45步之内解决，而且解的长度不应超过50步，则可设最大搜索深度为50。
广度优先搜索（Breadth First Search，BFS）尝试在不重复访问状态的情况下，寻找一条从初始状态到达目标状态的最短路径。BFS能够保证：如果存在一条从初始状态到目标状态的路径，那么找到的肯定是最短路径。BFS和DFS唯一不同的就是BFS使用队列来保存开放集，而DFS使用栈。每次迭代时，BFS从队列首部取出一个尚未访问的状态，然后从这个状态开始，确定能够到达的后继状态，如果已经达到目标状态，则结束搜索，任何已经在闭合集中的后继状态会被忽略，否则，新生产的后继状态将会放入开放集队列尾部，继续供后续搜索使用。使用BFS解题的过程可以使用伪代码描述如下（由于使用BFS解题和使用DFS解题差异非常小，请读者参照使用DFS解题的伪代码注释进行理解）：
bfs(initial, goal)
{
if (initial = goal) return "Solution"
initial.depth = 0
// BFS使用队列来存储开放集。
open = new Queue
closed = new Set
insert(open, initial)
while (open is not empty)
{
// 从队列首部取出尚未访问的状态。
n = head(open)
insert(closed, n)
foreach valid move m at n
{
next = state when playing m at n
if (closed doesn't contain next)
{
if (next = goal) return "Solution"
insert(open, next)
}
}
}
// BFS搜索结束仍未找到解则返回无解。
return "No Solution"
}BFS的优点是找到的解其长度必定最短，但缺点是空间占用较大，因为在迭代的每一步，BFS会将下一层的所有状态压入队列，如果搜索空间或解的深度较大，将会有大量的状态停留在队列中，很容易超出内存的限制。
如果给定的布局存在解，BFS能够找到一个最优解，但是可能需要访问大量的顶点，它并没有尝试对候选走法进行排序，相反，DFS是尽可能地向前探测路径，不过，DFS的搜索深度必须得到限制，否则它很可能会在没有任何结果的路径上花费大量的时间。
给定如图1-17所示的两个布局，直观来看，左侧布局要比右侧布局更接近目标状态，因为其“无序度”更小。直觉上，无序度较小的布局更有可能经过较少步骤的扩展后达到目标状态，相对的，无序度较大的布局在经过同等步骤的扩展后，到达目标状态的可能性要低。在搜索过程中，对于无序度低的布局可以优先考虑进行扩展，因为其更有可能在较短的步骤内到达目标状态。不过计算机并不具有类似于人类的直觉，需要程序员明确告知特定布局的无序度，或者指定一组规则，使得计算机能够按照规则计算布局的无序度。在物理学中，表示系统无序程度时有一个物理量，称之为熵（entropy），熵值的增加可以使用系统增加的热量及温度进行衡量。类似地，衡量给定布局的无序度，使用何种指标较为合适呢？观察左侧布局，之所以会得出其无序度较小的印象，是因为较多滑块处于其“正确”位置，而右侧布局则有相对较多的滑块未处于目标状态的“正确”位置，因此可以根据滑块与其“正确”位置的“距离”来度量布局的无序度。具体来说，就是使用滑块移动到其“正确”位置所需要使用的最少步骤数来量化某个滑块的无序度，所有滑块无序度的和即为整个布局的无序度。
图1-17 两个布局，左侧布局比右侧布局的“熵”要低。左侧布局到达目标状态最少只需要3步——RDR，而右侧布局到达目标状态最少需要15步——“LURULLDLDDRURDR”
定义3个函数如下。
f(n)：从初始状态开始，经过状态n，到达目标状态的最短走法序列。
g(n)：从初始状态到状态n的最短走法序列。
h(n)：从状态n到目标状态的最短走法序列。
对于给定的搜索问题，在得到实际解之前，状态n的f(n)、g(n)、h(n)值是未知的，那么是否有一种方法来估算这些函数值，从而能够为搜索提供剪枝的决策信息呢？也就是说，能否使用一种方法得到这3个函数的尽可能准确的近似估计值，在搜索的时候，依据该估计值将那些大于估计值而不可能获得解的搜索分支予以剪除，从而提高搜索效率。这就是以下介绍的A*搜索。
A*搜索在搜索时能够利用启发式信息，智能地调整搜索策略[14]。A*搜索是一种迭代的有序搜索，它维护一个布局的开放集合。在每次迭代时，A*搜索使用一个评价函数f*(n)评价开放集合中的所有布局，选择具有最小“评分”的布局。定义
其中3个函数定义如下。
f *(n)：估算从初始状态开始，经过状态n，到达目标状态的最短走法序列。
g*(n)：估算从初始状态到状态n的最短走法序列。
h*(n)：估算从状态n到目标状态的最短走法序列。
星号表示使用了启发式信息[5]，因此f *(n)，g*(n)，h*(n)是对实际开销f(n)，g(n)，h(n)的估算，这些实际开销只能在得到解之后才能够知道。f *(n)越低，表示状态n越接近目标状态。f *(n)最关键的部分是启发式地计算h*(n)，因为g*(n)能够在搜索的过程中，通过记录状态n的深度计算出来。如果h*(n)不能够准确地区分开有继续搜索价值的状态和没有价值的状态，那么A*搜索不会表现得比DFS更好。如果能够准确地估算h*(n)，那么使用f *(n)就能够得到一个开销最小的解。可以将A*搜索使用伪代码描述如下。
a_star (initial, goal)
{
if (initial = goal) return "Solution"
initial.depth = 0
// A*搜索使用优先队列存储开放集。
open = new PriorityQueue
closed = new Set
insert(open, initial)
while (open is not empty)
{
n = minimum(open)
insert(closed, n)
if (n = goal) return "Solution"
foreach valid move m at n do
{
next = state when playing m at n
next.depth = n.depth + 1
if (closed contains next)
{
prior = state in closed matching next
if (next.score < prior.score)
{
remove(closed, prior)
insert(open, next)
}
else insert(open, next)
}
}
}
return "No Solution"
}由于h*(n)在算法中非常关键，而且它是高度特化的，根据问题的不同而有所差异，所以需要找到一个合适的h*(n)函数是比较困难的。在这里使用的是每个方块到其目标位置的曼哈顿距离之和，曼哈顿距离是该状态要达到目标状态至少需要移动的步骤数。g*(n)为到达此状态的深度，在这里采用了如下评估函数。
其中h*(n)为当前状态与目标状态的曼哈顿距离，亦可以考虑计算曼哈顿配对距离。对于本题来说，效率比单纯曼哈顿距离要高，但比曼哈顿距离乘以适当系数的方法低[15]。
const int SQUARES = 4;
// 预先计算的曼哈顿距离。
int manhattan[SQUARES * SQUARES][SQUARES * SQUARES];
// 预先计算曼哈顿距离。
void getManhattan()
{
for (int i = 0; i < SQUARES * SQUARES; i++)
for (int j = 0; j < SQUARES * SQUARES; j++) {
int tmp = 0;
tmp += (abs(i / SQUARES - j / SQUARES) + abs(i % SQUARES - j % SQUARES));
manhattan[i][j] = tmp;
}
}
// 计算某个布局的评分。
int getScore(vector<int> &state, int depth)
{
int gn = depth, hn = 0;
for (int i = 0; i < state.size(); i++)
if (state[i] > 0)
hn += manhattan[state[i] - 1][i];
return (gn + 4 * hn / 3);
}迭代加深A*搜索（Iterative Deepening A* Search，IDA*）依赖于一系列逐渐扩展的有限制的深度优先搜索。对于每次后继迭代，搜索深度限制都会在前次的基础上增加。IDA*比单独的深度优先搜索或广度优先搜索要高效得多，因为每次计算出的开销值都是基于实际的走法序列而不是启发式函数的估计。使用IDA*进行解题的过程可以使用伪代码描述如下。
ida_star (initial, goal)
{
if (initial = goal) return "Solution"
// nowDepthLimit为当前搜索的最大深度限制。
nowDepthLimit = 0
// nextDepthLimit为已搜索状态的最小估计深度，是下一次迭代的参考深度限制。
// 初始时，其值设置为给定布局的评分。
nextDepthLimit = initial.score
// 在未找到解之前继续迭代。
while (true)
{
// 每完成一次迭代，更新DFS的最大深度限制。
if (nowDepthLimit < nextDepthLimit)
nowDepthLimit = nextDepthLimit
else
nowDepthLimit = nowDepthLimit + 1
nextDepthLimit = INF
// 根据上一次迭代得到的深度限制开始下一次DFS。
open = new Stack
closed = new Set
insert(open, initial)
// 当开放集不为空时继续搜索。
while (open is not empty)
{
n = pop(open)
insert(closed, initial)
foreach valid move m at n
{
next = state when playing m at n
if (next = goal) return "Solution"
if (closed doesn't contain next)
{
// 将评分小于限制深度的布局压入栈中，对于评分大于限制深度的布局，
// 取最小的评分值作为下一次DFS的预设深度。
if (next.score < nowDepthLimit) insert(open, next)
else nextDepthLimit = min(nextDepthLimit, next.score)
}
}
}
}
return "No Solution"
}IDA*搜索实际上可以看成使用启发式信息对DFS进行剪枝的过程。其中的剪枝阈值基于当前的实际走法步数和相对“智能”的对到达目标状态所需步数的估计。IDA*搜索的缺点是每次迭代均需要重新开始搜索，前一次迭代搜索的结果未能加以有效利用。在具体的实现中，避免重复生成之前的状态可以免去闭合集的使用，使得程序的效率更高。对于15数码问题来说，在移动空滑块时，如果当前将空滑块向右移动一个方格，那么下一步就应该避免将空滑块向左移动一个方格，因为这样会使得布局恢复到上一步的状态，对于将布局恢复到上一步状态的空滑块移动操作，需要将其剔除，这样就能够保证在DFS过程中遇到的布局是不重复的，从而免去了判断布局是否在闭合集中这一步骤，自然效率会提升。
参考代码
struct config
{
int hn, dir, r, c;
bool operator<(const config &cfg) const { return hn < cfg.hn; }
};
string directions = "URLD";
int offset[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}}; // 位置偏移量。
int puzzle[5][5]; // 记录布局。
int Hn[16][5][5] = {}; // 编号为i的滑块从正确位置移动到位置[r, c]时的熵的变化。
int dHn[16][5][5][5][5] = {}; // 编号为i的滑块从位置[r, c]移动到[rr, cc]时熵的变化。
int done; // 搜索是否结束的标志
int depthLimit; // 最大深度限制。
int path[64]; // 记录移动步骤。
void dfs(int hn, int gn, int dir, int missingr, int missingc)
{
if (hn + gn > depthLimit) return;
// 当布局的熵降低为零时，表明布局已经为目标状态。
if (hn == 0) {
done = 1;
for (int i = 0; i < gn; i++) cout << directions[path[i]];
cout << '\n';
return;
}
// 确定从当前布局能够得到的后续布局。
int cnt = 0;
config next[4];
for (int k = 0; k < 4; k++) {
if (k == dir) continue;
int rr = missingr + offset[k][0], cc = missingc + offset[k][1];
if (rr < 1 || rr > 4 || cc < 1 || cc > 4) continue;
// 更新布局的熵。
next[cnt].hn = hn +
dHn[puzzle[rr][cc]][rr][cc][missingr][missingc];
next[cnt].dir = k, next[cnt].r = rr, next[cnt].c = cc;
cnt++;
}
// 对具有较低熵的布局优先搜索。
sort(next, next + cnt);
for (int k = 0; k < cnt; k++) {
swap(puzzle[missingr][missingc], puzzle[next[k].r][next[k].c]);
// 记录移动的类型。
path[gn] = next[k].dir;
dfs(next[k].hn, gn + 1, 3 - next[k].dir, next[k].r, next[k].c);
if (done) return;
swap(puzzle[missingr][missingc], puzzle[next[k].r][next[k].c]);
}
}
void IDAStar(int missingr, int missingc)
{
// 通过累加每个非空滑块的熵来确定给定布局的熵。
int hn = 0;
for (int r = 1; r <= 4; r++)
for (int c = 1; c <= 4; c++)
if (puzzle[r][c])
hn += Hn[puzzle[r][c]][r][c];
// 每当搜索不成功时，搜索的限制深度递增1。
depthLimit = 0;
while (true) {
done = 0;
dfs(hn, 0, -1, missingr, missingc);
if (done) break;
depthLimit++;
}
}
// 判断给定的布局是否可解。
bool solvable(vector<int> tiles)
{
int sum = 0;
for (int i = 0; i < tiles.size(); i++) {
if (tiles[i] == 0) sum += (i / 4 + 1);
else {
for (int j = i + 1; j < tiles.size(); j++)
if (tiles[j] && tiles[j] < tiles[i])
sum++;
}
}
return (sum % 2 == 0);
}
int main(int argc, char *argv[])
{
// 预先计算正确位置为[r1, c1]的滑块移动到位置[r2, c2]时熵的改变。
for (int r1 = 1; r1 <= 4; r1++)
for (int c1 = 1; c1 <= 4; c1++)
for (int r2 = 1; r2 <= 4; r2++)
for (int c2 = 1; c2 <= 4; c2++)
Hn[(r1 - 1) * 4 + c1][r2][c2] = abs(r1 - r2) + abs(c1 - c2);
// 预先计算编号为i的滑块从位置[r1, c1]移动到位置[r2, c2]时熵的变化。
for (int i = 1; i <= 15; i++)
for (int r1 = 1; r1 <= 4; r1++)
for (int c1 = 1; c1 <= 4; c1++)
for (int r2 = 1; r2 <= 4; r2++)
for (int c2 = 1; c2 <= 4; c2++)
dHn[i][r1][c1][r2][c2] = Hn[i][r2][c2] - Hn[i][r1][c1];
int cases = 0;
cin >> cases;
for (int cs = 1; cs <= cases; cs++) {
vector<int> tiles;
// missingr和missingc表示空滑块所在的行和列。
int missingr, missingc;
for (int r = 1; r <= 4; r++)
for (int c = 1; c <= 4; c++) {
cin >> puzzle[r][c];
tiles.push_back(puzzle[r][c]);
if (puzzle[r][c] == 0) missingr = r, missingc = c;
}
// 若布局可解，则进行IDA*搜索。
if (solvable(tiles)) IDAStar(missingr, missingc);
else cout << "This puzzle is not solvable.\n";
}
return 0;
}强化练习
529 Addition ChainsC，652 EightD，10073 Constrained Exchange SortD，11163 Jaguar KingD。
提示
652 Eight中，由于8数码问题搜索空间较小，可以预先生成所有布局的走法序列，从而能够以查表的方式来输出解。或者使用IDA*搜索实时生成解。
10073 Constrained Exchange Sort题目描述中“l1~l2 = di”的含义为abs(l1 − l2) = di，即l1 − l2的绝对值为di。初看似乎可以使用双向搜索予以解决，但是由于搜索空间较大，很难在限定时间内获得Accepted。可将其转化为类似于三维形式的15数码问题，使用IDA*搜索加以解决。给定字符串ABCDEFGHIJKL，可将其转换为如图1-18所示的三维形式（其中L对应“空滑块”）。
图1-18 转换后的三维形式
11163 Jaguar King的解题关键是根据题目的约束条件寻找合适的启发式信息估算函数，使得能够较为准确地确定中间状态到目标状态所需的最少步骤数。观察题目所给定的位置变换规则，可以将其转换为与15数码问题类似的问题予以解决。由于此题所求的是达到目标状态的最少步骤数，在设置深度限制时，每迭代一次，深度限制增加1，而不能像15数码问题那样，每次迭代后深度限制可能增加不止1。因为15数码问题所求的不是最优解，所以可以在每次迭代时对深度限制的增量放宽。若15数码问题所求的是最短走法步骤，则每次迭代后深度限制的增量也需要限制为1。
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。当探索到某一步时，如果发现原先的选择并不理想或达不到目标，就退回一步重新进行选择。这种无法走通就回退，之后再前进的技术就称为回溯法，而满足回溯条件的某个状态就称为“回溯点”。在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成。这样的状态集合，其结构是一棵多叉树，每个树结点代表一个可能的部分解，它的儿子是在它的基础上生成的其他部分解。树根为初始状态，这样的状态集合称为状态空间树。
如果某个问题需要在所有可能的方案中确定某些方案是否符合要求，而且总的方案数不是太大（例如，约106种方案），那么使用回溯法是一种既简单又实用的方法。回溯法和穷举法类似，但有一定差异。穷举法要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能完整解的各个部分逐步回退再次生成解的过程。而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。在回溯法实现时，最关键的就是既不重复也不遗漏地遍历所有可能的方案，然后再对方案进行合法性检查。回溯法最常见的实现形式是递归，递归实际上就是在问题所对应的隐式图中进行深度优先搜索，因此需要标记已经访问的状态以便回溯。如果标记状态不当，很容易造成遗漏某些可能的解或者重复检查方案。
回溯法一般是从初始状态向终止状态进行搜索（或者相反），是单向的过程，也可以从初始状态和终止状态同时进行搜索，在中间状态相遇，此为双向搜索，双向搜索能够减少回溯中每增加一步所造成的状态的大量增长，有利于减少空间和时间消耗，但不是所有问题都适合使用双向搜索技巧，双向搜索只适用于记录状态不需太多空间的搜索类型题目。
对于大多数搜索类型的问题来说，它的问题空间都比较大，因此，需要根据问题的特点在回溯的过程中进行剪枝，将一些明显不可能得到解的搜索分支予以剪除，以提高效率。剪枝是一把双刃剑，剪枝过少对效率提升不明显，剪枝过多，用于确定是否剪除的计算量过大，反而会影响最终的效率，因此剪枝需要选择计算量较小而又能高效确定该分支是否可能走向可行解。需要具体题目具体分析，要靠解题者多接触、多练习、多思考，以期触类旁通、举一反三、熟能生巧。
对于更为复杂的问题，可以应用A*搜索，即启发式搜索，启发式搜索是根据特定问题的特点构造的代价函数，可以更为高效地判定当前搜索路径是否更有可能走向可行解。代价函数与问题密切相关。
对于类似于数独的精确覆盖问题，还可以应用称之为舞蹈链X算法的搜索技巧，舞蹈链X算法提高了标记和回溯的效率，因此可以较好地提高搜索效率。
[1] 应用回溯法的题目所蕴含的隐式图一般为有向图。如果读者对图论不太熟悉，那么这段关于回溯法和隐式图深度优先遍历关系的叙述可能不易理解，建议在学习本书第2章的内容之后再回过头来对这段话进行理解。
[2] Sultan，统治者称号。
[3] 读者可以参见3.2.3小节中的内容。
[4] 此处的深度优先搜索和后续的广度优先搜索是图遍历的两种基本方式，对图论及图遍历尚不熟悉的读者可以在阅读本书第2章的内容后再回过来理解本节内容。
[5] 自从1968年开发出此算法后，这个记法被广泛接受。
