00:00
各位同学,我们来把这个八皇后问题呢给大家写一遍,八皇后问题呢,也是放在递归S里面写的,那我直接这样写了,同学们直接上代码了啊,来,走一个,我们就取个名字叫king king。然后呢把皇后把,然后呢把主方法勾上。对主方法勾上,那同学们跟上我的思路,跟上我的思路,首先呢。我们先写一个方法,写一个方法可以将什么呢?可以将最后这个结果,就是同学们刚才老师给他分析的这个数组,能够把它打印出来,所以说我在这呢,先把这个数组定定下来。好吧,我,我先要做的第一件事情就是把这个数组定下来,说说,先写第一句话。就是干什么呢?我们先定义定义一个max表示表示什么呢?共有多少个皇后?
01:01
这个没有问题吧,所以说我直接定义一个max等于八八分后,紧接着呢,我们再定义一个数组,定义一个数组,刚才说的这个数组,这个数组呢R。二位用于干什么?保存保存,这个结果就是皇后,皇后。啊,就是放置放置位置的这个结果啊,比如比如这就是一个结果啊,待会儿呢,我们照着这个来进行一个验证,好比如说这里面有一个数组。啊,比如这有个数组,它呢到时间是这样,就是一个解法,你明白吧,好,那这个数组呢,我们就这样先定下来。是个一位数组啊,同学们,等于我new一个int max。这个没有问题吧。这个没问题,因为这个数组呢,到时候你在递归的时候肯定是共享的,我们刚才讲过递归它这个数据有可能是独立的,也有可能是多个站共享的,是不是,那这个时候显然要共享,因为你的棋盘只有一个。
02:08
明白这个道理吧,好,所以说下边呢,我们就先写个方法,将最后这个结果将皇后,哎,注意听啊皇后诶,将皇后摆放的位置。摆放的,诶摆放不。摆放。摆放的位置打印出来。位置输出吧,那这个地方其实特别的简单,咱们直接写一个方法就可以了,那就写啊,咱们就直接写个私有的private void print OK,那。打印这个数组其实特别简单,For循环一把就可以了,是不是for循环这个数组,那么在打印的时候呢,我们这样输出即可。怎么输出呢,我们让这个R。啊,咱们瑞。
03:02
几呢?I,为了好看呢,我们这地方来一个空格。是不是,那这个地方打一行,我们就先不要去换,等到他输出了一行过后,就是他只要输出一个,这个就是一个结果嘛,至少是一种解法,然后呢,我们就再换一行。好,第一个方法咱就写完了,写完了好第二种解法我们来看同学们还记不记得刚才我们在做分析的过程中,曾经有这样一句话,就是当我们把一个皇后放在一个位置过后,就判断是是不是OK的,就说判断是不是冲突。及判断,判断是否冲突。是否冲突?那同学们刚才讲过,所谓是否冲突指的是什么意思啊?是不是就是它是不是在同一行同一列,同一斜斜线呢?大家理解吗?那我怎么去根据当前这个设计思路来判断它是否冲突呢?来我写的专门写个方法,专门写一个什么方法呢,就是。
04:09
就是查看。查看,当我们注意听这句话啊,当我们放放置第N个皇后时。第N个就是我不知道是几个,反正是比如你放第一个呢,就。嗯,那就检测前面的N减一个,如果你放到第三个皇后,你就把放到第一个和第二个,检测一下跟不跟当前冲突,明白我意思吧,当我们放置第N个皇后的时候,就去检测。就去检测该皇后,注意听这句话啊,该皇后是否和和前面,前面已经。朱婷计划已经。摆摆放的摆放的,皇后冲突。
05:01
是否冲突?也就是说,如果我摆的第三个皇后,那我就得检查前面那个皇后跟我这个冲不冲突,你没有摆放的,肯定你还不用去检测,是这意思吧,所以说我们这地方写一个方法就可以了,Private。呃,怎怎怎么写private呢,那就是返回一个不值。那就写个价值判断吧,DGEDGE,好,那我给我传进来一个N。这个N代表的是第N个皇后啊,我做一个注释。N表示第N个皇后。表示放第第N个,第N个皇后能理解我的意思吧,那现在呢,我们就来。判断,首先我们先写一句话,看着啊。奥。大家看这段代码能不能看懂RI?呃,应该是一个for循环,为什么?因为你要跟前面都要判断,所以说我上来写个for循环。
06:00
什么for呢?I等于零,I小于加加。什么意思,就说我加一个N皇后摆放的位置过后呢,我就要把N前面几个皇后做一个检测,那怎么检测呢,If。看这个代码啊,RI,如果它等于R。嗯。各位同学,嗯,我写这句话你们看出来他是如果这个条件满足,代表什么意思?同学们能看出来如果我写了这句话,它代表什么含义吗?看出来没有,如果这个一旦相等,说明什么?说明它们是在同一列。是不是?因为你你你你肯定相同了的,同一列的嘛,对不对,好,那么这是同一列,那就不可以还有一个。
07:00
有有没有在同一个斜线,怎么写呢。好,我就写个写个算法啊,这个也很简单,那么同一个算法呢,我用的是绝对值。大家看这里我写个N减I,如果它等于了ma。点ABS,然后是RV。这个地方有点不好理解啊,大家认真听,N减掉一个二,我把这个全屏一下。谁呢,各位I?如果这个条件成立,我们就返回一个。Force。看到没有?就说这个地方,如果有这个条件成立,我们就返回一个false。返回一个方式,否则我们返回一个处代表不冲突,也就是说我跟前面三个一个都不冲突。那这地方我要做一个做一个说明,这句话先做一个说明啊,说明一把。
08:03
因为有点有点小小的绕,这句话表示判断,判断这个N,而N就就是第N个皇后,第N个N个皇后是否和前面的N减一个皇后在。同一列。这句话大家看这句话表示什么意思啊?这句话是在判断。表示判断第N个,第N个皇后是否和。和这个第个吧,因为你这个I在不停的变化嘛,对吧,表示和第第二个皇后。皇后是否在同意斜线?斜线这个地方呢,苏老师你这个为什么这样讲,刚才刚才我是不是讲过,我们这个这个数组它的特点是不是刚才我已经讲清楚了,是不是我在这讲过奥瑞它有一个特点是它的下标和这个值是有关系的,他下标呢,代表是第几个皇后,而他这个,而他下标刚好又又是第几行,同时它的列呢,它的列又代表是放在第几列的,所以说刚好利用这个特性。
09:31
刚好利用这个特性呢来写的,如果我这个数组不是这样定的,那这个算法就要发生变化,也就是说我判断是不是同一斜线跟我设计这个数组的结果是有密切关系的。打个比方。打个比方,比如说我,我以这个为例,比如说我在这放了一个位置,假设我把这个放在斜杠这个位置,大家想。他是不是是谁和谁相减,你们,你们拿这个看一下,假如我放了第二个皇后,放了第二个皇后,同学们看是不是N是二。
10:06
I级呢?NN传递在自己,N是N是二,就是代表第二个皇后,二减掉。一个一等于二。是不是,那同时你这个地方放的这个RN呢,是不是也是这个位置,是是几啊是一一。哦,我们我们来看看这个这个能不能说过去啊,比如说现在我我们判断第二个,比如说我N现在等于第二个方,那应该N等于一才对,因为我这个N是从零开始的,刚才我说错了,是不是因为N等于一的时候才代表是第二一个皇后,因为N从零开始走的嘛。所以如果这样子的话呢,我们看A,假设我把DN等于一的时候,其实第二个皇后把它放在哪里呢?放在这一个地方的。
11:00
呃,比如说我放在,呃,放在这个相当于这样子啊,那那这个有点不好讲啊,放在哪里呢?放在第第二列,第二列,呃,第二列其实它是一。是这意思吧,也就是说现在呢,N等于一和N等于它对应的对应的这个值,如果我放在呃呃,放在哪里呢?放在第二列,其实它也等于一,也等于一。是不是那这样子的话呢。可以看到,那就是。ABS注意看一下啊,这是有有点绕一减去。Ii现在是几呢?是零。零。它的这个绝对值ABABS是不是等于一啊?它是不是等于一啊。是吧,那同样我们在求这个。大家再看,呃,再看这这个对它求一个绝对值,是不是它也等于一,为什么呢?你看它这个等于a.ABS它的。
12:13
N等于一的时候,它是不是等于一啊,一减掉。0I等于零的时候,是不是你放在第一列,第一列是不是也是零了,所以说这个也等于一,因此它们相等。所以说用这个算法呢,就能不管你这个斜杠是放在哪个位置的,它们绝对值都是相等的,因此呢,用这个方法就能判断它是不是在同一斜线,就很简单一个想法,那有些同学老师还有一个问题,你没写哦,是不是我这个算法里面还少一个。判断什么呢?判断是否在同一行。哎,同学们,我为什么没有写是否判断同一行?因为你在进行这个便利的时候,你这个N本身代表行,他在不停的是递增了,因为你你放了第一个就放第二个嘛,他肯定不在同一行。
13:05
大家理解我在说什么吗?所以说,判是判断,是否在同一行,没有必要,没有必要判断。因为你这个N本身呢,N每每每次每次都在都在递增。大家理解我在说什么吧,是因此这个判断同一行没不需要写。不需要,他不可能放在同一行。好,那么这个假期我们就写完了。OK,好,这个写完了以后呢,下面我们接着再写一个,最后这个重要的方法叫什么呢?叫做check。哦,我们再写一个方法,因为这个是判断是不是,呃冲突嘛,那你你你判断冲不冲突,你首先得有一个回溯过程,你先你得放这个东西才行,你不放那他根本就没有办法去判断是不是,所以说我们现在呢,还要写一个方法,编写一个方法干什么呢?放置第N个。
14:03
第N个皇后。好,这个方法呢,我们就来开始玩一把啊,这个代码有点有点绕,同学们要认真听啊,Void check。什么意思,嗯。大家看这个check方法,就是我编写一个放置D勾皇后,在这里面我肯定要判断价值。那我开始写了啊,什么情况下代表找到了一个结果呢?先写一句话,如果我们这个N,因为你放,放弃N个皇后的,如果放的时候已经max了。说明什么?说明现在我们已经办到了第几个皇后了。如果恩。等于max是不是是不是这个,这个时候N就等于八了。如果这个条件满足是是不是N等于八了,而N等于八的时候,其实你是相当于在放第几个皇后了,同学们。
15:00
是不是在相当于放第九个皇后了呀?我不知道我有没有说清楚,因为N是从零开始走的,那么你在放第九个皇后,只有可能是第八个皇后已经放好了,才放第九个皇后,那也就是说第九个皇后根本不需要再放了,明白我的意思吧,也是当N等于八的时候,其实其实前其实八个皇后就已经放好了,能能理解我意思吗?其实八个皇后就已然放好了。这个啊,已然放好了。那既然如此,这个其实就已经是个结果了,是不是?如果是个结果,我们直接print。然后这个地方就return。因为你已经拿到一个结果,如果没有,没有到这个位置,应该怎么办呢?好,我们就应该。有一个循环不停的放啊,那现在呢,我们如果没有的话,就是就是一次放。啊,依次。依次放入皇后。
16:00
并并判断是否冲突。什么意思?就是要完成刚才老师讲的。这一套逻辑。这套逻辑,这套逻辑你看他这事整到第五步的时候,它会反复执行1234,其实就是递归。是不是这个道理,那现在老师就开始写了啊,我说了这个地方有一点绕啊,开始for循环,你一共要放几个皇后?是不是一共要放八个皇后,那就是max,你是不是一共要放八个皇后?同学们爱佳佳能理解吗?你是不是一共放八个皇后。所以说我。一共要放八个后,那在放的时候我应该怎么放呢?我先把当前这个候注意听这句话啊,先把。先把这个皇后先把这个,呃,应该怎么怎么写呢,先把。先把就先把当前这个皇后。这个皇后是不是第N个皇后啊,因为你这传的是N嘛,放到哪里呢,放到。
17:03
放到哪里,放到该行的该行注意听这句话啊,该行该行的第几个第几列。第一列。大家理解我就说什么,因为你上来过后先把这个黄是不是我们刚才讲过,嗯,我们刚才讲出的是不是放这个的时候,其实我是先放第一个,然后再放第二个的,是是这样玩的吧。好,所以说你先把它放在第一列,那怎么把它体现出放在第一列呢,是不是。N把它放在这里,因为你循环这个I等于零的嘛,但是你放完了过后,你到底有没有问题呢,是不是要去判断一下,判断当。放了当放置当放置,这个第个第N个皇后到哀烈士。埃列死是否冲突?
18:00
大家理解我在说什么吗?因为刚才这个冲突的方法咱已经写了,下级N。那么这个时候就有两种可能性,不冲突或者冲突,如果,如果这个地方我们判断这个价值N呢,它是不冲突的。不冲突,也就是说同学看再加紧,如果我们在这个地方,它整个返回是一个针,说明它冲突还是不冲突。说明他不冲突,因为它如果冲突,我们返回的是一个force,所以说这个地方一旦成立说明什么呢?不冲突。注意听啊,有有点绕,如果不冲突是不是我就接着。最近这句话接着。放什么呢?N加一个皇后。这就开始递归了。即开始立鬼。D知道我意思吗?那你放。这个皇后是不是就是N加一啊。
19:00
能理解我意思吗?就是你先判断放了DN过分后,到这个位置冲不冲突啊,如果不冲突我就放N加一,它不是又开始递归了吗?那有个问题,如果说价几N,它冲突怎么办呢?他冲突怎么办?冲突不要紧。不要紧,如果他这个条件不成立,不成立是不是相当于是冲突的,一旦冲突这个代码会回到哪里执行,他是不是又回到上面这个位置,然后把把这个当前这个N皇后这个位置放到下一列去了。我不知道有没有讲清楚。我把这句话写到这啊,如果冲突,如果冲突怎么办呢?冲突没有关系,如果冲突就干什么呢?就继续执行这一个R,它又回到执行这个RN了,这个N没有变化啊,RN等于I,但是大家知道它在回去回执行这个。
20:04
N加一的时候,它首先是L加加的。是不是相当于说这把这个冲突的这个位置往后,原先放的是I,但是呢,现在在把它在当前这一行,把它往后面再放一下,然后再去判断冲不冲突,如果不冲突我再放下一个,如果冲突我再回去再加压。OK,那就说如果重组继续执行呢?即将什么呢?即将这个R就是D。第N个第N个皇后放置在本行的,本行的,哎,别写错了啊,本行。的什么呢?这个呃,后一个后移的一个位置,后移的移个位置。位置好,同学们,这个代码就写完了。这个代码就写完了,大家有没有发现确实是已经写完了,因为你这个地方他每次都在不停的递归,还有一点同学们注注意啊,这段代码其实有有一点不太容易看懂,因为如果说你第一次看你老你你可能会觉得诶老师那你这样写的话,不是好像就得到只只得到了一个一个正确的摆法,不就退出去了,这样理解就没有理解回溯。
21:24
大家有没有发现,因为当你因为他在这个地方是一个for循环里面调用check。对不对,那意味着就说我们每放一个,每放一个。每放一个这个皇后里面都都会有一个这样的for循环。那什么意思?如果我有八个皇后?那我一共从理论上来说,我有八个,我这个check呢,循环的再。对最多如如果我有八卦后,对于对于同一层,对于同一层的吊柜调用都有八次调用这七个。
22:05
就同一层里面就有八八次一个切口。是不是所以说它这地方其实会产生这个回溯的。这点大家一定要理解啊,就是回溯这件事是OK的,是OK的,那么特别要注意一点。特别特别注意啊,特别注意。注意就是这个这个check壳呢,Check每一层。Check,它是它是每一次递归,递归时,递归时呃,进入到进入到这个check方法。这个中都有,都有什么呢?都有一套这个for循环。也就是说当这个,比如说我们怎么理解呢,就说当。这个有点不好讲啊,就是当我们进来一次在这个位置。
23:00
进来一次,他就他就先跑到下面去,先把这个走一圈,走一圈完了过后呢,不停的往走到假设走到这了,走到这是不是他就回退,回退到这一层,他会把这个往后面挪一下,挪一下是不是又进去一层,又又开始走一圈。是这意思吧,所以他这个回溯呢,其实就已经在这产生了。所以说我在这写着,他说每一个check里面都有一个for循环,都会调几次呢?调用啊,就是只要没有找到这个,这个事都会有一每一个check里,每一层这个check方法里面都有个for循环。那你每一次里面都会。放在不同的,所以说会产生回溯。因此。呃,因此会有回溯。回溯好代码就写完了,那代码写完了,我们再来调一调用用看看是否能够OK,这这个地方有点不好理解,就是说它为什么能够回溯起来哈,因为你你你到到时候你想一想嘛,进来一次先摆了一个位置,摆了一个位置他往里面走了,走完了过后,第一个位置摆完了后,假设这面成功,他回到这个位置又开始摆第又开始摆第二个位置,是不是又开始放它的下一个黄后网,而check里面又有这个for循环调用,因此回收会产生。
24:16
好,那现在这个代码说完了,过后呢,我们来进行一个简单的测试吧,那么。
我来说两句