00:00
同学们,我们继续来讲递归的第二一个应用实例,八皇后问题。八皇后问题,八皇后问题呢,这里面也会用到回溯,我们首先把这个八皇八皇后问题再做一个简单的说明哈,八皇后问题呢,它是一个古老而著名的文著名的一个问题,这是回溯算法的经典案例。那么这个问题呢?他其实是1848年就提出来,说在八乘以八的一个国际象棋上摆上八个皇后,使其互相不能攻击,也就是说什么意思呢?就是说任意两个皇后都不能处于同一行,也不能处于同一列或者同一斜线,问一共有多少个解法?有多少种这个?摆放的方式,那么著名的数学家高斯,他曾经认为有70种解法。70种,我看是不是70种啊,我看看最先前呢,咱们这不是有一个这个案例吗。啊,他说有76种,76种解法,那么在1841854年的时候呢,有一个作者发表说只有40种不同的解,后边我们用这个回溯,或者用说用图论方法呢,解,解决出来有92种解法,的确是92种,那现在呢,我们就用这个程序的方式来给大家进行一个解解答哈,那这样子首先在讲之前,我们是不是仍然给大家探讨一下。
01:27
他的思路就是。不管是高斯说的76种,还是另外那个作者说的40种,我们先不管那么多,我们先把他的一个思路给大家捋一捋,那么首先呢,我们看他的一个八皇后问题算法的思路分析。这是我总整理了一下啊,他是先将第一个皇后放在第一行的第一列,这个很好理解,然后呢,把第二个皇后放在第二行的第一列。明白我的意思吧,然后判断是不是OK的,就是看他是不是相互攻击。
02:05
那么如果不OK呢?就把第二个皇后放在第二列,第三列,依次把所有的列放完,找到一个合适位置,然后把第二个皇后在第二行放好以后呢,再放第三个皇后,第三个皇后也是从他的第三行的第一列,第二列依次依次。摆一个位置,而且每放一个皇后过后呢,也要看他是不是OK的,就说他是不是相互攻击。如果说呃,当我们把第八个皇后。摆在第八行的一个适当位置,就得到了一个正确解。也就得到一个解了,得到一个解过后呢,注意第四行很重要,当得到一个正确解的时候呢,这个站回退到上一个站,也就是回退到上一个站,然后就开始回溯。即将第,即将第一个皇后,他什么意思开除呢?即把第一个皇后放在第一列的所有正确解全部得到。
03:06
明白我的意思吧,就是说,呃,待会我们举个例子说他在回回溯的时候呢,是从那个是从那个站顶开始回溯的。也就是说他首先把第一个皇后,我们不是有第一个皇后放在第一行的吗?啊,第一行的第一列吗?把假设这个地方,先把这个所有的解全部拿到,拿到以后呢,回头再把第一个皇后摆在第一行的第二列,然后又向这边走一圈,又得到所有的解。循环得到1234啊这个地方还写了少写了一个1234步。这样子来做的。那么嗯,那这样子的话,大家可能还是有点不明确,说老师你这个我有点不太明白,这样子我们呢,还是用Excel表把这个图解给大家画一下,帮助大家理解老师在说什么好不好,那么我们来看一下吧,我们来看一下OK。
04:03
说这地方有。有一个八乘以八的。国际象棋。国际象棋。那么按照刚才。刚才老师这一个思路,他应该是。应该是怎怎么去理解呢。好,同学们注意听啊,应该怎么去理解呢?我把这个放到这。啊,一一定要先把这个理解了,不然的话,待会我把代码写出来,你也不知道我在写什么。明白意思吧,就说你可能你你不把这个搞定的话,待会你你不理解老师写什么好,然后这是第四一步,然后这是第五一步,好,我们来把这个思路捋一捋,他首先先把第一个皇后放在第一行的第一列,那现在呢。我用一个小圆圈儿代表一个皇后。好吧,这个小圆圈呢,为了醒目,我标成一个红红色的,假设这是一个皇后,放这儿了,第一步就做完了。
05:06
第一步就是那第一二步开始,他把第二一个皇后呢,放在第二行的第一列看,他就是看把这个第二个皇后放好以后看看这个第二个皇后跟已经。排好的已有的这个皇后是不是相互攻击。显然。这个是相互攻击的。是不是这个是相互攻击,所以说他就。只能摆在这个位置,摆在这个位置过后呢,同学们。这个时候他发现也是相互攻击的。于是他把在。下一个位置。摆在下一个位置呢,再摆我们的,哎,他发现这个摆好了以后就不跟他攻击了,不跟他攻击呢,再摆我们的第三个皇后。第三个皇后呢,它也是从这地方开始去摆的,但是注意一个问题啊,他在摆的这个过程中。摆的这个过程中,有可能会回溯到这个地方。
06:04
有可能会回溯到这个地方,把这个位置重新修改,因为他可能发现在后面摆的过程中,这个位置是不可以的,理解我在说什么意思吗?就是发现这个位置不行。啊,这个就有点不好理解,他在回溯的时候还会回来调整这个位置,所以说他,呃,他最后呢,这个第二行,其实他应该摆在哪个位置呢?我们讲过它应该是摆在第五一个位置。就是他通过回溯最后摆到这儿了,那么第三行应该摆在哪里呢?摆在。这个位置。OK,好,呃,那下一个呢,我们继续来讲啊,下一个第四一个应该摆在第几个位置呢?我看啊,应该摆在第六个位置,我记得第二个位置。第二个位置,再下一个呢。再下一个。我们看一下啊,再下一个,我看看应该摆在第三个位置。对,第三个位置再下一个,我们应该摆在哪一个位置呢?看啊1234567这个位置,然后再下一个。
07:05
再下一个摆在第应该是第二个位置啊,第二个位置,那再下一个应该摆在第几个位置呢?摆在第四个位置,好,这个就是第一种摆法。那么第一种摆法,摆完了过后,注意听,注意听,他开,他就开始回溯。他在回缩的过程中,他会怎么办呢?他先尝试着把这个位置,把最里面这个位置摆在这这个地方,看看是不是又是一种解法摆在,如果这个不行,摆在这个位置是不是解法,摆在这个位置是不是解法,摆在这个位置是不是解法,如果这些都不行的话呢,会怎么办呢?它会把这一这一层注意听回回溯是从这儿开始,他把把这个往后面挪一下,再把这个地方重新摆一遍。明,明白我在说什么吧。那么如果发现这个地方都不OK,都不OK,它会再到这一这个位置开始回溯,于于是它会往下移动,再来开始进行这个回溯,所以说他在进行回溯的时候呢,大家看这里,当得到一个正确解释,当站回推到上一级这个站的时候呢,就开始回溯,即他会把。
08:14
第一个皇后放在第一列的所有的可能性全部得到。全部得到,然后再把这一个。第一个皇后摆在第二个位置,然后再把这个流程再来玩一遍。理解我在说什么吧,这个是这个是有一点难度的啊,就说代码很简单,但是代码不是很简单,代码相对来说没有那么复杂,但是理解起来有一定难度,所以说,所以大家一定要理解,当得到一个正确解的时候呢,它在回溯的时候,其实是从。这一层开始回溯的。那么整个这一层回溯完了,又回溯这一层,再回溯这一层,再回溯这一层,再回溯这一层,再回溯这一层,最后回溯到第一个皇后,第一个皇后回溯完了之后,把这个位置往后面挪一下,把刚才流程再来玩一遍。所以说这个回溯法大家不要小看,其实它的效率并不高。
09:05
为什么不高呢?待会我们写写一下,你就知道一个八乘以八的一个八皇后问题,你知道它一共会去检测多少次吗?他大概要检测15000多次,也就是说他在整理检测有没有冲突的这个过程中,一共要去执行15000多次,一个八乘以八的。输入这个效率并不高,但是呢,它也算是一种解法。对,也算世界吧,后面呢,有些人提出对他的一个优化,比如说加入这个贪心算法进行优化,那是我们后面再再去聊的话题,好吧,那现在呢,思路我们也有了啊,是不是也有了,那呃,我再多说一句,就说理论上呢,按理说根据刚才老师讲解的,我们不是八乘以八吗。按理说我们应该去创建一个二维数组来表示起来,但是实际上我们可以通过算法呢,用一个一位数组就可以解决问题,也就是说待会呢,我们会这样做,我们会创建一个一位数组,这个数组呢有八,然后呢,我们每得到一个解法,就把它的它的位置记录下来,比如说我得到一个解法是零,刚才那样摆的啊,零,四。
10:19
呃,七然后呢五然后二,我记得是二对不对,然后是六,然后是一,然后是三,也就是说假设我们有一种解法是这样写的,就表示什么意思呢?替我说。听我说啊,就表示我们第一个皇后放在第一行的。第一列,因为下标为零,表示第一列,第二个皇后放在第二一行的。第五列大家注意啊,我们这个位置刚好。刚好可以跟它的下标进行一个匹配,也就是说零就代表第一行的。第一列明,明白我意思吧,如果五的话,那就代表我第二一个皇后。
11:05
第二,一个皇后放在是第二个皇皇后放在第二行的第五列,也就是说这个地方代代表的是呃,代表的是第几列,而它所在的下标呢,代表的是行,我再把这个注释一下。对于这个,对于这个一位数字来说呢,它的下标。就是它的下标表示。第几行及第几个皇后?这个大家知道我在说什么吧,然后呢,具体的这个值就是RV,它这个下标。下标对应的这个值,这个值就是这个value value表示表示。呃,第个皇后,但实用是第加一个皇后。皇后。啊,放在哪里呢?放在D加一行的,加一行的D多少列呢?D这个value加一列。
12:10
这样我就可以用一个一位数组来把这个二位数组表示出来。我不知道,我不知道我讲没有讲清楚啊。我不知道有没有讲清楚,但是呢,呃,其实这样讲已经比较清楚了,如果说呃,如果说还不理解,待会我们用这个案例就能让大家理解的更清楚,好吧,好,同学们,那关于我们这个八皇后的一个思路分析呢,就到这儿,我先把代码整理一下,待会呢,我们就写代码了,好吧,先把刚才的思路捋一捋,那刚才。刚才老师呢,大致把这一个八皇后问题做了介绍,同时呢也对八皇后问题的解法做了一个分析。好,我先来说一下八皇后问题。八号问题,其实呃,从问题的层面来说还是比较清晰的,就是说白了就是摆皇后,然后不要互相攻击及这样一个条件就可以了。
13:07
最后这个白矾呢,统计出来一共有92种。也就是说你写完这个算法过后呢,你要去测试是不是,呃,随便拎几个出来看看对不对就行了。这是问题,然后问问题呢,这有个图,待会儿呢,我们可以用那个用那个游戏来进行测试,对吧,我们可以用游戏来进行测试,好的,然后呃,然后呢,这边我们也大致把这个八皇后的一个思路做了一个分析。把这个思路咱们分析到这个位置啊,思路分析到这里。诶,我把它放在这个位置,就是八皇后它的一个算法的思路分析。大概大致呢,咱们分成了。分成了五步,好,这有一个示意图,我把我把这个示意图呢,也给同学们,呃,拿到这来。呃,其实说白了就是把刚才这个步骤呢,给大家演示了一遍。
14:03
对不对,演示了一半。好,这是它的一个简单的示意图。还有一点,我在我在正式写代码之前呢,我这里有一个说明,我做了一个什么说明呢,就说待会我在解题的时候呢,我不会去创建一个二维数组来表示起来,我直接用的一个一位数组,那么这个一位数组呢,大家可以看到它有八个元素,八个元素呢,它的这个下标就代表是第几个皇后,当然因为下标从零开始的,其实就是I加一个皇后,后面这个值呢,就代表这个皇后放在。这个皇后其实刚好也是放在第几列的啊,第几行的,然后呢,他这个呃值呢,就代表放在第几列,你明白这个意思吧,比如说后面我们得到一个解释,04752613就代表第一个皇后。放在第一列,第二一个皇后,放在第五列,第三个皇后,第三个皇后刚好也是第三行嘛,放在第八列,明白这意思吧。
15:04
好,我把这个思路已经给同学们聊清楚了啊好,下面呢,我们就准备代码实现,代码实现我们放在下一个视频。
我来说两句