00:00
那么玩一把,我们先测试一把,测试一把,看看这个八皇后是否正确,八皇后是否正确啊,有有点绕啊,但是呢。我觉得还是讲的比较清晰吧,就是。呃,慢慢去理解都没有问题,我六一个K。八号后。然后呢,同学们,现在我们用这个八皇后点。他的一个方法什么方法呀。Check,我们先从零开始放,也就是说我放的时候先放零。有放偏放第一个皇后偏棒第一个皇后的时候呢,他先把第一个皇后放在第放在第一行的。一这是零嘛,先放,把第一个方放在第一行的第一列,然后往里面去判断是不是这个道理,然后这个回溯的时候又又开始不停的回溯,完了以后在check的过程中,里面就会打印。
01:01
是不是会打印吧,好,那现在我们一执行看这个效果就出来了。大家看,很神奇吧?很神奇。那到底一共有多少个解法呢?一共有多少解法呢?来,同学们,我写一个count,我把它统计一下,呃,因为count的时候呢,我们用一个静态变量才能把它统计出来,Count int,比如说count默认为零。OK,那为了统计这个解法呢?那一共打印了多少次,是不是就代表?一共有几个解法,那现在呢,我在print里面把这个count加加。这个没毛病,就说因为你只有有一个正确的解法,我才会print。好,现在我把这个print给大,给大家输出来,就是解法的次数。就说一共注意听啊。一共有。有多少次解访呢?解访?
02:02
好,那现在呢,我把这个进行一个简单的格式化。把count给各位朋友输出一把。没毛病吧,来各位同学自行词一共有多少种呢?92种解法。92种解法,而且同学们有没有发现跟刚才老师讲的是完全一样的,你们有没有发现,看这里。同学们看这里啊,你们有没有发现跟我刚才分析的完全一样,是他先把。也就是说他先把我看这啊,你们有没有发现他其实在回溯的时候,他是先把这个第一个皇后放在第零个位置,所有解法全部做完再解。把第一个黄喉放在。第一行,第一行的第二列的解法全部接到。而回溯应该是怎么产生的呢?就是相当于我们可以这样理解,就是当他得到一个减法的时候。他先回,他把这个解法回到,他先回到这个位置,然后呢,看这个一下面的一下面这个四,就是如果针对上面这个,它应该是把这个最后这个把这个三变成4567,然后呢测试一下看看O不OK,如果这个不OK,他就回溯到这个解法的上一级,以此类推,最后他发现这都不行,回收到哪里才OK呢?回收到这个零的时候才发现。
03:25
这个零不要变,然后呢,第二一个黄后放在第五个位置才会有一个解法,所以它回溯的是实际上是从是从放置的,呃,就是相当于说从占底回溯的是不是,就是当他得到一个解法过后,他先回溯到上一层,然后再回,然后就开始回溯了,以此类推,所以你看每为什么每次是先把。你看这个地方是先把零做完了,才才去做一的一做完才去做二的二做完,你看二二这个减法就很多了。就是当第一个黄后放在第二个位置,其实方法很多,第三个呢,把第一个黄放在第三个位置,其实有更多方法,把第呃第一个黄后放在第一行的第五个,第五列有更多的解法。
04:09
看到这个东西了没有,一共有92种。一共有92种,好同学们,那么这些解法呢,其实可以可以,我们可以简单测试一下,到底OK还是不OK,我们来测一下看看我,呃,这个方法我们以前测过没毛病,现在呢,我们随机的找,再找两种来进行一个测试,看看到底行不行啊,到底行不行。好,我们来简单的测试一把。打开我们的。呃,浏览器,然后呢,我们在这里。哦,我们这里。来找到这个游戏的地址,我们来给大家跑一下。现在呢,我们呃,来给大家简单的运行一下,看看行不行哈,来把地址拷贝到我们这个位置。
05:02
好,我我们现在呢,就是随机的测两个,测两个就肯定92种,不可能完全每个都去给他测一遍,这是不现实的,对吧,我就找两个吧。呃,找哪一个呢?随机的,我们先找找一个最后这个啊,找一个最后这个好,我们来看一下。好,我把这个打开。往里边搜一搜,搜一下啊。往这边挪一下,大家看看这个解法。嗯,把这个往这边挪一下。好,我们对着这个来写,好好,先放呃,第一个皇后,第一个嗯,第第一个皇后,我们放在第一行的第嗯第八列。第二一个皇后放在大家看这里啊,这把第二个皇后放在我们第二行的第四列。
06:00
把第三个皇后放在第三行的第一列零嘛。是不是?没问题吧,把第四一个皇后放在第四行的第三列。好,没有问题,好,然后第五一个皇后放在第五行的第六列,因为这是这是五嘛,对吧,这是五好那就是呃,下一行的第六列,第六列别写错了啊,也没有问题,把下一个放在第六行的第二列。是这吧。也没有冲突,把下一个放在第七行的第七列。是不是这个位置。也没有冲突,也是OK的,把最后一个放在第八行的第五列。是不是这个位置啊,同学们。Winner。OK。很神奇啊,很神奇,这个解法就可以了,那其他我就干脆就不一个去测了,你们去测一下应该都没有没有问题,因为这个算法没有毛病,那代码就是OK的,好同学们经过这个测试呢,我们发现没有任何问题,好现在我把这个代码给各位同学简单的板述一下,刚才呢。
07:17
我们已经把这个说完了,好,那现在呢,我直接把这课代码给他拿过来就OK了,因为刚才整个这个思路分析呢,在我们的。程序里面其实也做了说明了,如果你听不懂的话呢,那只有一个办法,就是多听几遍,然后自己画画图好吧。这个有些东西还是需要自己去动动脑筋的,因为因为八皇后问题,他采采用的这个回溯还是很多,其实你们可以去试一下,你们知道这个回溯一共有多少次吗?就是他一共光这个判断是不是冲突,应该至少都在1万多次以上,你们可以试一下,就说光这个价值。
08:01
你们看我们这里是不是有个价值啊,这个价值他在进行判断有没有冲突的时候,你们可以来统计一下一共有多少次,我给大家写写一个变量,你们看一下static,比如说我写一个呃,统计它的价值的GGE的一个count。你们你们可以看一下这个他一共去判断了多少次冲突。那么掉一次我们就加一次。是这意思吧,我们把这个价值打出来看一下。就是一共判断。判断这个冲突的次数。冲突的次数是这么多次。啊,这个次数是相当庞大的啊,相当庞大的至少得一万一万多次,至少得应该是15000,一万一一点五万以上,1.5万以上,那么我们运行一下。大家看这么多次。
09:02
就是你得到这个解,解法看起来好像很快,其实他掉这个方法都掉了15720次。光判断冲突都有15000多次,所以说我们说这个回溯的效率呢,因为因为没办法,这个本身就比较复杂对吧,所以他这个回溯的效率其实呃,在一定程度上还是比较慢的。那么能不能优化呢?我们后面再去谈这个啊,优优化的时候,我们再后面再再谈这个算法,OK,好,那现在我把这个代码给各位朋友板书到笔记中去。OK,好,直接将代码放到这里来。好,同学们,那关于我们这一个递归的八皇后问题,就给同学们介绍到这里。
我来说两句