八皇后問題：在8*8的棋盤上放置8個(gè)皇后，保證任意兩個(gè)皇后之間不能相互攻擊。（即沒有兩個(gè)皇后是在同一行、同一類粘都、或者同一對角線上）
- 計(jì)算出8皇后或者N皇后可能的所有擺放結(jié)果。其中8皇后共計(jì)有92種不同的解刷袍。
- 打印顯示出來其中的一種擺放結(jié)果或者所有的結(jié)果。
1. 回溯法：
回溯法：即試探法樊展，系統(tǒng)的搜索所有解的方法呻纹。具體思想：從一條路往前走，能進(jìn)則進(jìn)专缠，不能進(jìn)則退出來雷酪，換條路再走。解決八皇后問題的經(jīng)典算法涝婉。
偽代碼如下：
- 將棋盤存到一個(gè)N*N的矩陣中（8*8）哥力，二維數(shù)組。
- 算法開始墩弯，清空棋盤吩跋，當(dāng)前行設(shè)為第一行，當(dāng)前列設(shè)為第一列渔工。
- 在當(dāng)前行當(dāng)前列的位置是否滿足條件：經(jīng)過這一點(diǎn)的行锌钮、列、以及兩條斜線上沒有其他皇后引矩。若滿足：轉(zhuǎn)到步驟4梁丘；若不滿足，轉(zhuǎn)到步驟5旺韭。
- 滿足步驟3的條件：在當(dāng)前位置放置一個(gè)皇后氛谜，分以下情況：
- 若當(dāng)前行不是最后一行，當(dāng)前行設(shè)為下一行区端， 當(dāng)前列設(shè)為當(dāng)前行的第一個(gè)待測位置(不一定是第一個(gè)位置)值漫；轉(zhuǎn)到步驟3。
- 如果是最后一行珊燎，記錄下這個(gè)解惭嚣。記錄之后遵湖，若當(dāng)前不是最后一列，當(dāng)前列設(shè)為下一列晚吞；若當(dāng)前列是最后一列延旧，即最后一列，回溯槽地，清空當(dāng)前行迁沫，然后當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測位置捌蚊。
- 不滿足步驟3的條件集畅，分以下情況：
- 如果當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列缅糟，繼續(xù)步驟3挺智。
- 如果當(dāng)前列是最后一列，回溯窗宦，即赦颇，若當(dāng)前行已經(jīng)是第一行了，算法退出赴涵，否則媒怯，清空當(dāng)前行及以下各行的棋盤，然后髓窜，當(dāng)前行設(shè)為上一行扇苞，繼續(xù)步驟5。
算法改進(jìn)：把棋盤存儲(chǔ)為一個(gè)二維數(shù)組寄纵，然后需要在第i行第j列放置皇后時(shí)鳖敷，根據(jù)問題的描述，首先判斷是在第i行是否有皇后擂啥，由于每行只有一個(gè)皇后哄陶，這個(gè)判斷也可以省略，然后判斷第j列是否有皇后哺壶，這個(gè)也很簡單屋吨，最后需要判斷在同一斜線上是否有皇后，按照該方法需要判斷兩次山宾，正對角線方向和負(fù)對角線方向至扰。相對較為復(fù)雜。
若把棋盤存儲(chǔ)為一個(gè)N維數(shù)組q[N]资锰，數(shù)組中第i個(gè)元素的值代表第i行的皇后所在列的位置敢课，這樣便可以把問題的空間規(guī)模壓縮為一維O(N)，在判斷是否沖突時(shí)也很簡單，首先每行只有一個(gè)皇后直秆，且在數(shù)組中只占據(jù)一個(gè)元素的位置濒募，行沖突就不存在了，其次是列沖突圾结，判斷一下是否有a[i]與當(dāng)前要放置皇后的列j相等即可瑰剃。至于斜線沖突，通過觀察可以發(fā)現(xiàn)所有在斜線上沖突的皇后的位置都有規(guī)律即它們所在的行列互減的絕對值相等筝野，即| row – i | = | col – a[i] | 晌姚。這樣某個(gè)位置是否可以放置皇后的問題已經(jīng)解決。
1. 遞歸實(shí)現(xiàn)
代碼如下
//八皇后問題解法
public class Queen {
static int count=0; //統(tǒng)計(jì)解的個(gè)數(shù)
static int N = 8; //皇后個(gè)數(shù)：8
static int [] q = new int[N];
//大小為8的數(shù)組：數(shù)組下標(biāo)表示：row歇竟，數(shù)組[i]對應(yīng)內(nèi)容：col挥唠。
public static void print()
{//打印解的坐標(biāo)位置及圖像
for(int i=0;i<N;i++)
System.out.println(i+" "+q[i]);
for(int i=0;i<N;i++)
{
System.out.print("|");
for(int j=0;j<N;j++)
{
if(j==q[i])
System.out.print("Q|");
else
System.out.print(" |");
}
System.out.println();
}
}
public static boolean canPlace(int i,int j)
{//判斷坐標(biāo)(i,j)處是否可以放置皇后
for(int k=0;k<i;k++)
{
if(q[k]==j||Math.abs(i-k)==Math.abs(j-q[k]))
return false;
}
return true;
}
public static void queen(int row)
{//遞歸，從第row行開始循環(huán)每一列
if(row==N)
{
count++;
if(count==1)
print();
}
else
{
for(int j=0;j<N;j++)
{
if(canPlace(row,j))
{
q[row]=j;
queen(row+1);
}
}
}
}
public static void main(String[] args) {
for(int i=0;i<N;i++) //初始化
{ q[i]=-1;}
queen(0);
System.out.println(count);
}
}
2. 非遞歸實(shí)現(xiàn)
public class Queen {
static int N=8;
static int[]q=new int[N];
static int count=0;
public static void print()
{
for(int i=0;i<N;i++)
System.out.println(i+" "+q[i]);
for(int i=0;i<N;i++)
{
System.out.print("|");
for(int j=0;j<N;j++)
{
if(j==q[i])
System.out.print("Q|");
else
System.out.print(" |");
}
System.out.println();
}
}
public static boolean canPlace(int i,int j)
{
for(int k=0;k<i;k++)
{
if(q[k]==j||Math.abs(i-k)==Math.abs(j-q[k]))
return false;
}
return true;
}
public static void queen()
{
int row=0,col=0;
while(row<N)
{
while(col<N)
{
if(canPlace(row,col))
{
q[row]=col;
col=0;
break;
}
else
{
++col;
}
}
if(col==N)//q[row]==-1
{
if(row==0)
break;
else
{
--row;
col=q[row]+1;
q[row]=-1; //把上一行皇后的位置清除焕议，重新探測
continue;
}
}
if(row==N-1)
{
count++;
if(count==1)
print();
col=q[row]+1;
q[row]=-1;
continue;
}
++row;
}
}
public static void main(String[] args) {
for(int i=0;i<N;i++)//初始化
q[i]=-1;
queen();
System.out.println(count);
}
}
