由于我水平有限,本文参考了网上的各个做法,选取了我最能理解的解法,我尽量地解释这个解法来检验我对本问题的理解程度(只写出最终的解法数量)。八皇后问题讲的是8个皇后棋在一个8*8的棋盘上,谁都不能攻击到对方,皇后的攻击方向有横竖斜三个方向,不同的摆放形成不同的解法。其实就是一个给皇 ...
由于我水平有限,本文参考了网上的各个做法,选取了我最能理解的解法,我尽量地解释这个解法来检验我对本问题的理解程度(只写出最终的解法数量)。
八皇后问题讲的是8个皇后棋在一个8*8的棋盘上,谁都不能攻击到对方,皇后的攻击方向有横竖斜三个方向,不同的摆放形成不同的解法。
其实就是一个给皇后找位置的游戏,先确定第一个皇后的位置,剩下的逐行根据规则确定,成功的输出,失败的返回上一个位置试下一个位置,直到8个皇后全部选好位置。
以下是具体的代码(java)
1 //8皇后问题 2 public class Queen 3 { 4 private int[] column; //同列是否有皇后,1表示有,0表示没有 5 private int[] rsl; //右上至左下是否有皇后 6 private int[] lsl; //左上至右下是否有皇后 7 private int[] queen; //皇后编号 8 private static int num;//答案数量 9 public Queen()10 {11 column=new int[9];12 rsl=new int[17];13 lsl=new int[17];14 for(int i=1;i<=8;i++) 15 {16 column[i]=0; //初始定义全部无皇后17 }18 for(int i=1;i<=16;i++)19 {20 rsl[i]=lsl[i]=0; 21 }22 queen=new int[9];23 }24 public void backtrack(int i) //这里的i才是行数25 {26 if(i>8)27 {28 num++; //最后大于8表示8个皇后都找到了位置,解答数加一29 }30 else31 {32 for(int j=1;j<=8;j++)33 {34 if((column[j]==0)&&(rsl[i+j]==0)&&(lsl[i-j+8]==0))//判断横竖斜有没有皇后35 {36 queen[i]=j;//皇后位置37 column[j]=rsl[i+j]=lsl[i-j+8]=1;//设定为占用38 backtrack(i+1); //循环调用39 column[j]=rsl[i+j]=lsl[i-j+8]=0;//再定义无皇后 40 }41 }42 }43 }44 public static void main(String[]args)45 {46 Queen queen=new Queen();47 queen.backtrack(1);//开始回溯法,从行1开始48 System.out.println("\n解答数为"+num); //输出总解答数 49 }50 }
海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理:https://www.xlkjsw.com
原标题:八皇后问题简易解答(回溯法)
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。