八皇后問題：在8*8的棋盤上放置8個(gè)皇后，保證任意兩個(gè)皇后之間不能相互攻擊。（即沒有兩個(gè)皇后是在同一行、同一類、或者同一對(duì)角線上）
- 計(jì)算出8皇后或者N皇后可能的所有擺放結(jié)果。其中8皇后共計(jì)有92種不同的解。
- 打印顯示出來(lái)其中的一種擺放結(jié)果或者所有的結(jié)果。
1. 回溯法：
回溯法：即試探法，系統(tǒng)的搜索所有解的方法。具體思想：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退出來(lái)，換條路再走。解決八皇后問題的經(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è)待測(cè)位置(不一定是第一個(gè)位置)；轉(zhuǎn)到步驟3。
- 如果是最后一行，記錄下這個(gè)解。記錄之后，若當(dāng)前不是最后一列，當(dāng)前列設(shè)為下一列；若當(dāng)前列是最后一列，即最后一列，回溯，清空當(dāng)前行，然后當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測(cè)位置。
- 不滿足步驟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è)也很簡(jiǎn)單，最后需要判斷在同一斜線上是否有皇后，按照該方法需要判斷兩次，正對(duì)角線方向和負(fù)對(duì)角線方向。相對(duì)較為復(fù)雜。
若把棋盤存儲(chǔ)為一個(gè)N維數(shù)組q[N]，數(shù)組中第i個(gè)元素的值代表第i行的皇后所在列的位置，這樣便可以把問題的空間規(guī)模壓縮為一維O(N)，在判斷是否沖突時(shí)也很簡(jiǎn)單，首先每行只有一個(gè)皇后，且在數(shù)組中只占據(jù)一個(gè)元素的位置，行沖突就不存在了，其次是列沖突，判斷一下是否有a[i]與當(dāng)前要放置皇后的列j相等即可。至于斜線沖突，通過觀察可以發(fā)現(xiàn)所有在斜線上沖突的皇后的位置都有規(guī)律即它們所在的行列互減的絕對(duì)值相等，即| 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]對(duì)應(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; //把上一行皇后的位置清除，重新探測(cè)
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);
}
}
