八皇后问题java解法
程序员文章站
2022-04-15 19:01:37
...
八皇后问题
八皇后问题是:在八行八列的格子上放8个皇后(棋子),使得任意两个皇后都攻击不到对方,即使得他们都不在同一行同一列和同一斜线上。
int[] result ;//最终的结果数组
int queenNum;// 皇后的数量,N皇后
int k = 0;
public void static main(String[] args) {
queenNum = 8;
result = new int[queenNum];
questionN(0);
}
// 核心回溯算法
public void questionN(int n) {
if(n == queenNum){
k++;
Log.e("-----","解法:"+k);
for(int i = 0;i<queenNum;i++){
Log.e("-----","第"+(i+1)+"行放置位置:"+(result[i]+1));
}
return ;
}
for (int i = 0;i<queenNum;i++){
result[n] = i;
if(checkValid(result,n)){
questionN(n+1);
}
}
}
// 检验合法性
public boolean checkValid(int[] result,int n){
for(int j = 0;j<n;j++){
if(result[j] == result[n]){// 是否在同一条直线上
return false;
}else if(Math.abs(result[j]-result[n])==Math.abs(j-n)){//是否在同一条斜线上
return false;
}
}
return true;
}
上一篇: 安卓使用zxing生成二维码
下一篇: IDEA