問(wèn)題描述:
八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：如何能夠在8×8的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后,使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后渗磅？為了達(dá)到此目的焕梅，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上攻泼。八皇后問(wèn)題可以推廣為更一般的n皇后擺放問(wèn)題：這時(shí)棋盤(pán)的大小變?yōu)閚×n，而皇后個(gè)數(shù)也變成n。當(dāng)且僅當(dāng)n = 1或n ≥ 4時(shí)問(wèn)題有解凤藏。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ---------來(lái)自<維基百科>
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? 個(gè)人思路:
max表示n個(gè)皇后 用array[n]表示皇后在第n+1行,array[n]列,比如array[0] = 8 意思為:該皇后位于第1行第8列的坐標(biāo);
排列樹(shù)與子集樹(shù)的區(qū)別在于子集樹(shù)不需要初始化而排列樹(shù)需要,此初始化內(nèi)容為眾多可能解集合(注:是可能解,不一定為正確解)中的一個(gè)
初始化為a[]數(shù)組(1-n隨意排列);
將a數(shù)組的值向array中輸出,初始傳入n為0;表示該皇后在第一行,但具體哪列不確定,此時(shí)初始化的a數(shù)組就起到了作用,a[n]表示在n+1行的第a[n]列, 將其賦值給array,即: array[n] = a[i];
(因?yàn)閍[]中只是可能性,所以要將所有可能性用for循環(huán)表示.即:for(int i = n;i < max ; i++);
然后更新a數(shù)組 swap(a,n,i) (意為 既然已經(jīng)使用過(guò)a[i]那就用原本的a[n]替換a[i] 保證列值不重復(fù))
更新后判斷該位置是否與已經(jīng)存在的皇后的位置沖突(同斜線) 已經(jīng)通過(guò)a數(shù)組和n已經(jīng)去除掉同行同列的可能;n保證不同行,a[i]保證不同列;
如果合法,則進(jìn)入n+1;重復(fù)討論n+2個(gè)皇后的位置 /如果不合法,交換回之前位置(只有合法之后才能占該列值) i++;
當(dāng)i++到for循環(huán)結(jié)束,也就是說(shuō)該皇后在這一行所有列中都沒(méi)有找到合適自己的位置,回退,即該方法執(zhí)行結(jié)束,重新討論之前上個(gè)皇后的位置;
代碼如下:
? ? ?
public class NQueen {
int max = 8;
int array[] = new int[max];
int[] a = { 8, 2, 3, 4, 5, 6, 7, 1 };
public void backtrack(int n) {
if (n == max) {
? print();
? return;
} else {
? for (int i = n; i < max; i++) {
? array[n] = a[i];
? swap(a, n, i);
? if (nice(n)) {
? ? backtrack(n + 1);
? }
? swap(a, n, i);
? }
}
}
public boolean nice(int n) {
for (int i = 0; i < n; i++) {
? if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {
? return false;
? }
}
return true;
}
public void swap(int[] a, int i, int j) {
int tem = a[i];
a[i] = a[j];
a[j] = tem;
}
int k = 0;
public void print() {
++k;
System.out.print("第" + k + "種解法:");
for (int i = 0; i < array.length; i++) {
? System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
new NQueen().backtrack(0);
}
}
