問題描述：將八個皇后放在棋盤上，任何兩個皇后都不能互相攻擊（即沒有任何兩個皇后在同一行、同一列或同一對角線上）如圖所示
在本文中，對於兩題採用了稍微不同的解法，但都使用的是一維數組。 6.20中，要求求出一個有效佈局，我建立了一個有八個元素的一位數組，通過隨意打亂數組的值，通過值與下標的比較，直至得出一個有效佈局；6.22中，要求求出所有有效佈局，這裡我使用了八進制數，遍歷了從001234567-076543210的所有數字，透過將其轉換為八進位字串，每位與其下標相比較，輸出滿足條件的佈局。以下將對實作原理和方式進行詳細介紹。
Part 1 如何判斷是否為有效佈局
我們將棋盤視為一個8*8矩陣，範圍均為0-7。觀察左邊的圖，可以發現，其佈局可以用一組數對來表示(從上到下)，即(0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7， 2)。用一個陣列來表示，即int []list = {0, 6, 3, 5, 7, 1, 4, 2};
顯然，這是一個有效佈局。下面我們就要考慮一個問題：在有效佈局中，下標和其在數組中對應的值，即i 與list[i] 有什麼關係嗎？
這裡我們設list[i] = k; list[j] = q; (i > j)，它們滿足一下兩個條件（在紙上畫出來比較容易懂）：
1、 k != q;
2、 i - j == k - q 或i - j == q -k （題意得）
為了保證，k != q, 這裡宣告並初始化陣列 list， 使得list[i] = i。 然後隨機打亂數組，然後檢查是否符合條件2
複製代碼代碼如下:
// 建立並初始化數組
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
list[i] = i;
// 隨機打亂數組
public static void randomizeArray(int [] list){
int arrSize = list.length;
int ranIndex;
for(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
if(ranIndex != i){
int temp = list[i];
list[i] = list[ranIndex];
list[ranIndex] = temp;
}
}
}
6.20 的程式碼主體如下
複製代碼代碼如下:
// 6.20 遊戲：八皇后
public void solveEightQueens(){
int arrSize = 8;
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
list[i] = i;
int count = 0;
boolean notValid = true;
while(notValid){
count ++;
notValid = false;
randomizeArray(list);
for(int i = 0; i < arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // 檢查是否符合條件
notValid = true;
break;
}
}
if(notValid) break;
} // end of outer for loop
} // end of while
// print the result
int i;
System.out.println("O(∩_∩)O哈哈~, I have tried " + count + " times, and eventually succeed.");
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
Part 2 求所有有效的佈局
由於6.22 要求求出所有有效的八皇后佈局，隨機打亂數組的方法已經不再適用，只好尋求一個可以遍歷所有可能的方法。一個最直接的方法是，使用八層for循環，不過代碼量太大，而且腦袋容易暈掉，所以不採用這個方法。
仔細觀察Part 1中數組的值，可以發現，它們都在0-7之間，因此使用八進位int數進行遍歷可以保證包含每一個排列。由於八位數字各不相同，因此可能的排列有8! = 40320種，而八進制數總共有8^8 = 16777216個，因此可能的比例佔40320/16777216 = 1/416，得到的這40320個排列還要進行檢查才能篩選出最終有效的佈局。這個方法效率還是有點低，不過暫且還沒想出更有效率的。
複製代碼代碼如下:
// 6.22 遊戲：多種八皇后問題的解決方案(利用int值遞增，然後將其轉變為八進位字串，再進行檢查）
public static void solveEightQueensMethod(){
int start = 001234567; // 八進位
int end = 076543210; // 八進位
int count = 0; // 計算有效的佈局數
for(int i = start; i < end; i++){
boolean isValid = isValid(i);
if(isValid){
if(++count % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // 輸出有效的佈局數
}
// 檢查number 是否為有效佈局
public static boolean isValid(int number){
String numOct = Integer.toOctalString(number);
int arrSize = numOct.length();
if(arrSize==7) { // 如果number第一位是0，則產生的字串只有七個字符
numOct = '0' + numOct;
arrSize ++;
}
for(int i = 1; i < arrSize; i ++){
for(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false; // 同一列
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false; //同一條對角線
}
}
return true;
}
Part 3 延伸：生成組合的問題
去年在一個筆試上，有這樣一道題。給定一個序列，輸出所有的組合。比如，
「123」 的輸出： 1， 2， 3， 12， 13， 21， 23， 31， 32， 123， 132， 213， 231， 312， 321
「abcd」的輸出： a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., abcd, ...
在6.22中，求出所有的八皇后佈局，所使用的方法是透過遞增int 型數，再逐一檢查。上面的問題可以用類似的方法來解決。不過效率有點低，如果有更有效率的辦法，求高手指點