算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
Sudoku
Loading...
来自 Peking University 的课程
算法基础
284 个评分
从本节课中
深度优先搜索（2）
本模块继续通过两道例题，强调了两种最通用的剪枝方法：可行性剪枝和最优性剪枝的应用。可行性剪枝即在寻找解的过程中，预判出从当前状态出发不可能找到解，从而不再从当前状态继续；最优性剪枝就是记录到目前为止找到的最优解，当发现正在探索的解其代价已经不小于最优解，或预测出其最终代价必将不小于最优解，则停止当前解的探索。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
啊同学们好，下面呢我们来看一个简单也比较暴 力一点的这个深度优先搜索机。
所谓暴力就说技巧性不是很高。
这个题目叫做Sudoku。
Sudoku就是数独，好像是日本人发 明的一种填数字的游戏。
那它要做的事情呢就是 在一个9x9的这个矩阵上面，
一共有81个方格嘛，然后有的格子里面就已经填了数字，然后你要在 空白格子里面再填上1到9，这样的数字。
那填完以后呢，你要使得在这个矩阵中的每一列 或者每一行，以及每一个小方块儿。
3乘3个小方块儿。
3乘3个小方块儿一共就有9个对吧？每一列每一行每一个小方块儿 里面所有的数字都出现。
那当然每个数字也只能出现一次了对吧？ 这就是著名的数独。
那现在， 这个题说的就是，给的输入数据，这就代表 一个数独的这个矩阵。
这里面为0的地方就代表是空格，你要往里头填数字。
那么你解出来的答案就是一大堆数字的一个矩阵，它满足数独所要求的那些条件。
那么这个题，我们想 怎么做呢？
也没有什么特别好的办法，你就可以搜索， 来试试，对吧？
那你完全纯暴力的搜索是不行的。
这个完全纯暴力指的就是你枚举每种这个换数字的这个方案。
然后你把一种放数字的方案排好以后，你再去，全部都排完以后你再去判断这个方案是不- 是合法。
那你这么做，你做判断的时间就太晚了，这可能就会超时。
所以我们这里面要做一些剪枝。所谓剪枝就是预先 判断出不可能的情况，就不用再试下去了，对吧？
这个预先判断体现在什么地方呢？ 就体现在我们放入一个数字的时候
我就要看，我放进去这个数字是不是合法的，如果不合法我根本就不放。
我不要等把所有数字都放完了，然后一起来判断整个局面是不是合法。
我每放一个数字都要去判断一下这个数字放在那儿，到底合法不合法。
也就是说我们放入一个数字以后，就要做个标记。
假设这个数字放进去是合法的，那我们先放进去以后就要做一个标记。
这个标记就表示在刚刚放过数字的那一行、那一列 以及那个小块儿，已经放过这个数字了。
那么以后我们就 不会在同一行同列或同一小块儿，放同样的这个数字。
那总之一个数字它在每一行、每一列以及每一个小块儿都有标志。
然后我们把数字放到一个 格子里面，我们就会把它对应的行列以及小块的标志都记成1。
这样就能够避免 在同一行同一列以及同小块儿放相同的数字。
基本上就这样啦。
所以我们关键要看一下这个 这个程序的逻辑是怎么样的，怎么样用程序来实现这个事儿。
那如我所说，这里我们就设置了一个rowFlags这个数组。
这个数组rowFlags[ i][num] = 1 就表示在第 i 行已经放进了数字 num。
那colFlags就是，那colFlags[i][num] = 1 就表示在 第 i 列已经放这个数字 num。
然后blockFlags， blockFlags[i][num] = 1 表示在第 i 个小块儿已经放这个数字。
那这小块儿编号就是从左到右、从上到下进行编号的。
左上角的就是 第 0 块儿，然后最右下角的就是第 8 块儿。
那我们现在，整个棋盘就是board[9][9]。
然后我们需要一个struct，用来表示这个一个位置。
然后呢，我们现在需要把所有空白的位置都收集起来放到一个数组里面，所以我们用一个ve- ctor<Pos>。
这样类型的东西。
blankPos用来存放所有空白位置。
空白格的位置。
那我们有一个空白格的 有一个格子的位置我们会想要知道它到底是属于哪一个小块儿，它属于的小块儿的编号。
那么就有GetBlockNum就有列号 由行列号能够求小块儿，对吧？ 这个具体的都没什么可说了。然后，
这有个SetAllFlags就是，指的就是，我现在如果把 数字 num 放入 (i,
j) 这个位置， 或者我把数字 num 从 (i,
j) 这个位置拿走，那么我需要影响哪些标志。
额，那么，额， 它要影响3个标志，对吧？
一个就是rowFlags[i][num]。如果你把数字放到 这个 (i,
j) 这个位置了，那么数字在第二行的标记， 我们就要记成 1。
那如果是你从第二行拿走这个数字num了，那我们就要把它的标记记成0。
我们为什么会拿走啊？ 因为我们做搜索的时候有需要 做回溯对吧？
那我们有时候就会把一个数字放进去 然后搜一遍，然后再把它拿走，再用别的办法再搜，是吧？
那总之这个就是设置行标记、设置列标记，然后设置这个小块儿标记。
然后我们要把一个数字放到 (i,
j) 这个位置的时候我们马上就要判断数字放在这里到底合适不合适，那怎么判断呢？
那我们就，就看，如果第 i 行没有放过 num， 第 j
列也没有放过 num，而且就是这个 (i,
j) 这个位置所在的小块儿也没有放过 num 。那我们就认为是合适。
所以只要这3个标记同时都 不为真，那我们就认为这个 num 放在 (i, j) 是Ok的。
好啦那我们这Dfs深度优先搜索的函数写起来就比较容易啦。
这 Dfs(int n) 指的是我要处理前n
个空格子，就要往前 n 个空格子里面去放这个数。
那我们把所有的空格子都放到一个数组里面了，对吧？ 这个Dfs n 表示处理前 n 个空格子。
那如果 n 小于 0 就说明已经没有空格子要处理了，那我们就 return true，就说明什么啊？
我已经找到一种解决的方案了。
那么 在接下来我们就要看一下这个空格子的位置在哪儿。
空格子的位置就是blankPos[n] .r
和blankPos[n].c，因为现在我们要处理前 n 个空格，我们就从第 n 个空格处理开始，啊。
然后接下来我们就要往 r、c 这个地方去放数字。
那放数字 就会有9种选择。
所以我枚举9种选择，那么从 1 一直到 9，枚举 9 种选择。
然后我们就要把num放到 r、c。
那如果num确实能够放 到 r、c 那我就放了呗。
就board[r][c]就能等于num，就把数字放到，num放到 [r][c] 这个位置了。
然后我就要设置3个标记，对吧？ 把3个标记都设置成1。
然后接着我就再去处理前 n-1 个空格，对吧？ 所以就Dfs(n-1)。
那如果Dfs(n-1)成功了，那我们就return true就说明我们已经找到了一个方案，那就Ok了是吧？
那如果这个Dfs没有return true就说明我们刚才的 那个把num放在r、c最后会导致失败。
那这样的话我们就要把num从r、c拿走，所有就SetAllFlags( r,
c, num, 0)，意味着把num从r、c拿走。
然后呢我们就回到这个循环， 在r、c这个位置去放别的数字，是吧。
那如果这个循环走完了它也没有从 这里返回，那么Dfs的返回就是false，就整个不行。
然后在main()里面就很简单了我们就读入 test的case的数目，然后把这所有的flags都全部都置成0。
然后我们blankPos这个数组，把它清空。
然后呢我们就读入了 这样一个9x9的矩阵。
那 每一个元素都是一个字符吧。
然后如果有一个字符它的 值是字符0，那我们就认为这是一个空格。
那既然是个空格，我们 我们就会把这个
空格的位置给它push到这个blankPos这个数组里面去。
那如果board[i][j]它这个 不是空格呢？
那我们 就意味着往 [i][j] 这个位置放了一个数字。
这个数字是什么？数字不就 是 c-'0' 的ASCII码，对吧？ 那现在要，我们把[i][j]这个位置放这个数字，
那我们就要SetAllFlags把这个数字所定的标记给它置上。
是吧？ 这个数字就是board[i][j]，对吧？
然后， 数据都读完了我就可以用Dfs去做搜索了，对吧？
那我们现在实际上有多少 个空格子呢？ 就有blankPos.size()这么多个空格子。我们给它编了号就是从0到
blankPos.size()- 1
所以我们Dfs的时候就倒着， 就说我们先要处理前这个
blankPos.size()- 1 这么多个空格，也就是所有的空格了。
然后，如果这个函数返回是为true就说明 我们找了一份解决方案，然后我就把整个board给它输出就Ok了，对吧？
而这个题它有一个奇怪的地方就是，我们这块等于说这是从 最后一个空格的位置往前去搜，对吧？
那实际上你也可以从第一个空格去搜到最后一个空格，那就是另外一种顺序。
那按理说，在这个题目里面你是空格 从前往后搜。
所谓前就是靠左上角，后就是靠右下角。
按这个题目呢，按这个题目实际上你这个空格从前往后搜还是从后往前搜应该没有什么差别。
但这个题的数据可能出的有一点点问题。
可能 它出数据的那个程序它有一定的倾向性，所以就会使得
我们像这样倒着来搜速度就很快，如果你正着搜，比如这个Dfs(0)，
从0一直搜到n-1这样的办法，结果说不定就会超时。
反正这一点就提醒我们有的时候相同的搜索顺序，
等价的，基本上没有什么差别的搜索顺序我也可以换一下 不同的顺序试一下。
说不定数据有什么倾向性。我们这个顺序搜就能 过，那个顺序搜可能就过不了。
Ok，这道简单题就是这样。
