1.八皇后問題介紹
image.png
2.思路分析
1.將第一個(gè)皇后放在第一行第一列
2.將第二個(gè)皇后放在第二行第一列,判斷與第一個(gè)皇后是否沖突升略,如果沖突屡限,將它放在第二列品嚣、第三列......直到找到不沖突的位置
3.將第三個(gè)皇后放在第三行第一列钧大,判斷是否沖突啊央,如果沖突眶诈,將它放在第二列瓜饥、第三列......直到找到不沖突的位置
4.之后幾列和2逝撬,3步驟相同宪潮,尋找一個(gè)正確解,如果找不到就將前一個(gè)皇后向后移一位狡相,重復(fù)1,2檩淋,3步驟
- 找到一個(gè)正確解后,從棧頂元素開始蟀悦,在這一行找其它位置不沖突的正確解氧敢,到棧底時(shí)就會(huì)找到第一個(gè)皇后放在第一行第一列的所有正確解
6.將第一個(gè)皇后放在第一行第二列,重復(fù)2浙炼,3唯袄,4,5步
注:這里我們用一個(gè)一維數(shù)組來存儲(chǔ)恋拷,數(shù)組中第一個(gè)元素表示第一個(gè)皇后放在第一行的第arr[0]+1列,第二個(gè)皇后放在第二行的第arr[1]+1列.......,第i個(gè)皇后放在第i行的第arr[i]+1列.arr[i] = val表示第i+1個(gè)皇后放在第i+1行第val+1列宴偿。
3.代碼實(shí)現(xiàn)
package com.yc.day03.recursion;
public class Queue8 {
//定義皇后個(gè)數(shù)及數(shù)組
int max = 8;
int arr[] = new int[8];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("共有%d種擺法\n",count);
System.out.printf("共判斷了%d次",judgeCount);
}
/**
*擺放皇后
* */
public void check(int n){
if(n==max){//當(dāng)n==max時(shí)诀豁,是第九個(gè)皇后了,表示前八個(gè)皇后已經(jīng)擺放完成
print();
count++;
return;
}
for (int i = 0; i < max; i++) {
//將第n+1個(gè)皇后擺放在第n+1行第i+1列
arr[n] = i;
if(judge(n)){//如果不沖突娩践,擺放下一個(gè)皇后
check(n+1);
}
//如果沖突了烹骨,將第n+1個(gè)皇后往后移arr[n]=i+1,由于這里i++,所以不用做操作直接進(jìn)入下次循環(huán)
}
}
/**
* 擺放第n+1個(gè)元素時(shí)判斷是否與前面所有元素沖突
* */
public boolean judge(int n){
judgeCount++;
for (int i = 0; i < n; i++) {
/**
* 說明:
* 1.arr[i]==arr[n]用于判斷第n+1個(gè)皇后是否與第i+1個(gè)皇后在同一列
* 2.Math.abs(n-i)==Math.abs(arr[n]-arr[i])用于判斷第n+1個(gè)皇后是否與第i+1個(gè)皇后在斜線上
* */
if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
return false;
}
}
return true;
}
/**
* 打印數(shù)組
* */
public void print(){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}