如何解决八皇后问题


问题

八皇后问题指的是在 8*8 的棋盘上,放入 8 个皇后,并且保证在每一行、每一列、以及对角线上都不会一起出现两个皇后(国际象棋的规则里面,皇后的侵犯规划是其地址的反正两条线以及地址的两条对角线),那么该怎么摆放这 8 个皇后呢?一共有多少种摆放方法?

思路

第一种思路,8*8 的棋盘上一共有 6V E N J4 个格子,现在要将 8 个皇后放入到这 64 个格子当中,就是数学里面的组合数 ,然后从这些组合里面选择i e ) q v | `出契合条件的摆放方法。这种做法虽然没错,可是 这个组合数的核算成果太大了,一共有 4426165368 种组合,核算量偏大。

第二种思路,由于每个皇后不能在同一行、同一列上,咱们在放入第一个皇后时,随意选择一行_ B R a 1 ],咱们有 8 种选择;再放入第二个皇时,此时咱J F 1 6 @ v }们必定不能放在第一个皇后地址的行和列了,所以只有 7 种选择了;再接着咱们放入第 3 个皇后,相同的道理,只能有 6 种选择了;以此类推,当咱V – n B * F s u们放入第% ; & x e . 8 个皇后的时分,就只有 1 种选择$ @ 4 n X ? w h &了。所以这U b ^ D ) l 0 q 种思路,咱们一共有 8 的阶R L % $ s ~ ~ @乘种选择,即 40320 种选择,然后咱们再从这 4 万多种组合里面选择出契合条件的摆放方法,看上去 4 万多比较前面的 44 亿,小了许多,也算是一种不错的解法了b p * b o } l S

第三种思路:在第二种思路的基础上,咱们在放入第二个皇后的时分,只考虑了与第一个皇后不同列、不同行,没有考虑对角线的问题,所以认为第 3 个皇后在放入的时分有 7 中选择,那假设咱们把对角线的问题考虑进去,那` ~ 7 A } ]第二个皇后的选择就少了一点。相同,在放第 3 个皇后的时分,咱们再把前面两个皇后的对角线考虑进去,第三个皇后的选择也少了,以此类推,到放第 8 个皇后的时分,选择就更少M @ 6 O c q j了,甚至在放第 5 个、O ^ $ d R K D K _第 6 个的时分,就出现了没有任何选择可以选的状况了,也就是死路了。这样整体下来,出现的组合状况必定是远远小于第二种思路的 4 万多种组合。

关于第三种思路,假设咱们出现了死路怎样办?假设咱们在放第 5m U J ; n 个皇后的时分,出现了无论怎样放第五个皇后,都会不满足要求,这个时分就阐明,前面 4 个皇后的摆放有问题。那怎样呢?咱们可以先回退到第 4 步,修正第 4 个皇后的摆放方位,然后再继续检验摆放第 5 个皇后。假设第 5 个皇后仍然无法摆放,那再回到第 4 步,再修正第 4 个皇后的方位。假设出现第 4 个皇后可以G % 1 f 9 | `摆的当地全都检验了,第 5 个皇后仍是没T l d N # |有当地可放,那这个时分就阐明,第 3 个皇后的方位摆放出了问题,所以重q 0 ; z M r _ o d新回到第 3 步,假设后边仍旧出现死路,那就依次往后回退,直到找到适E i i j宜的摆法。

了解数据结构与算法的同学这个时分必! e ~ I ] V J C u定想到了,这种思H g a路就是回溯思想,先从某一条路初步走,一条路走到黑,出现死胡同了,就回W ? F到上一个路口(回溯),从另一个方向再次动身,又出现死胡同了,就再回来刚刚的路口,直到将该路口的一切岔道走遍了,假设仍是走不通; ^ } b . 2,就继续向前回溯q C G 3 H T v A `,回到上上个路口,直到找{ 5 = o 6 b +到出路中止。

回溯的思想很简略,那么代码该怎么完成呢?完成回溯法最常用的办K | 9 !法就是运用递归了,下面运用回溯思想,用递归代码来完成上面 8 个皇后的摆放问题N . S

回溯法代码完成

首要咱们界说一个长度为 8 的6 2 X *数组:int[] result,用来存放每个皇后摆放在哪I ] o ) S s % F H个当地,数组的下标标明存放的是第几行的皇后,元素的值标明的是该行的皇后摆放在哪一列。例如:result[0] = 4 标明第 0 行中的皇后放在第 4 列k [ { – s e * h

别的再界说一个方法 putQueen(row),含义是往第 row 行中放入一个皇后,代码J / M f a T w U f的骨架如下:

//用一个数组存放- ~ o ;每一行的皇后的方位J k m D h 3 8 c T,数组的下标标明的是行,元素的值标明的是该行的皇后摆放在哪一x ] } v
pj M _ublicint[]result=newint[8];

/**
*往第row行中放入皇后,row最初步从0初步
*@paramrow第几行
*/

publicvoidputQueen(introw){
if(row==8){4 X { / o Y @ `//假设等于8标明8个皇后都摆放完了{ T _ 7,直接回来即可
printQueen();//打印
return;
}
for(intcolumn=0;column<8;column++){//检验分别将皇后放在第0-7列中
if(isAccessible(row,column)){//在真W 9 - s ) }正将皇后放进棋盘之前,先判别这个方位能不能摆放皇后
result[row]=column;//放入皇后
putQueen(row+1);//鄙人一行中放入皇后
}
}
}

在每次往某一行的某一列中放入皇后之前,咱们需要判别一8 0 M A d r + B e下,该行该列是不是在前面几个皇后的侵犯规划之内(行、列、对角线)。所以界说了一个方法 isAccessible(row, column),该方法就是来判别该行该列能不能放入皇后。判别逻辑是什么呢?就是从其时行依次向上遍历,判~ s S别前面几行的皇后的侵犯规划是不J o * : % J T是会覆盖到第 row 行第 column 列,具体代码如下。

/**
*判别第row行,第column列能不能摆放皇后
*@return
*/

privatebooleanisAcceh ! b o t # Issible(introw,intcolumn){
intleft=column-1;//对角线左上
intright=column+1;h ; F G D//对角线右上
//从其时行的上一行初步,向上遍历(没有必要判别其时行的下面几行了,因为下面@ z Q w P % S 8几行必定d B O没有放皇后啊)
for(int` E $ Li=row-1;i>=_ ? ` $ X 3 s0;i--){
if(result[i]@ M 5 C 7 E v==column)returnfalse;//其时列上不能有皇后
if(left>=0&&result[i]=] ! 6 6 .=left)returnfalse;//左上对角线上不能有皇后
if(right<8&&resuV W P B o Q Zlt[i]==riv 8 ] & A E s jght)retur{ 1 Cnfalse;//右上对角线上不能有皇X ~
left--;
right++;
}
returntrue;
}

最后为了方便闪现皇后f [ Y – ( j *的摆放方位,写了一个打印 8*8 棋盘的方法。

privatevoidprintQueen(){
for(introw=0;row<8;row++){
for(intcolumn=0;column<8;column++){
if(result[row]==coy $ ~lumn)Sy4 W ) p Y k 6 ustt & { y V r Y uem.out.print("Q");
elseSystem.out.print("*");^ / m 2 e
}
System.out.println();
}
System.out.println("=========================");
}

终究工作成果一共有 92 中摆放方法。

总结

回溯法的思想很简略,就是在岔口上先选择一条路走下去,走不通了,就回退到上一步,继续走,直到检验一切的G [ #选择中止。虽然思路简略,但完成回溯法的代码相对而言,不是那么好写,常常出现一看就会,一些就错,笔者作为一名菜鸟就是如此,常常写错,尤其是边界值的当地,因此也主张咱们多亲自动手敲敲代码。

其他

  • redo log —— MySQL宕机时数据不丢掉的原理
  • 索引数据结构之B-Tree与B+Tree(上篇)
  • 索引数据结构之Br e m t –-Tree与# a b wB+Tree(下篇)
怎么处理八皇后问题

发表评论

提供最优质的资源集合

立即查看 了解详情