快捷導(dǎo)航

java實(shí)現(xiàn)八皇后問題示例分享

更新時間：2014年03月10日 16:44:59 作者：

這篇文章主要介紹了java實(shí)現(xiàn)八皇后問題示例，八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出

問題描述：將八個皇后放在棋盤上，任何兩個皇后都不能互相攻擊（即沒有任何兩個皇后在同一行、同一列或者同一對角線上）如圖所示

在本文中，對于兩道題采用了稍微不同的解決方式，但都使用的是一維數(shù)組。6.20中，要求求出一種有效布局，我建立了一個有八個元素的一位數(shù)組，通過隨意打亂數(shù)組的值，通過值與下標(biāo)的比較，直至得出一個有效布局；6.22中，要求求出所有有效布局，這里我使用了八進(jìn)制數(shù)，遍歷了從001234567-076543210的所有數(shù)字，通過將其轉(zhuǎn)化為八進(jìn)制字符串，每位與其下標(biāo)相比較，輸出滿足條件的布局。下面將對實(shí)現(xiàn)原理和方式進(jìn)行詳細(xì)介紹。

Part 1 如何判斷是否是有效布局

我們將棋盤視為一個8*8矩陣，范圍均為0-7。觀察左邊的圖，可以發(fā)現(xiàn)，其布局可以用一組數(shù)對來表示(從上到下)，即(0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7， 2)。用一個數(shù)組來表示，即 int []list = {0, 6, 3, 5, 7, 1, 4, 2};

顯然，這是一個有效布局。下面我們就要考慮一個問題：在有效布局中，下標(biāo)和其在數(shù)組中對應(yīng)的值，即 i 與 list[i] 有什么關(guān)系嗎？

這里我們設(shè) list[i] = k; list[j] = q; (i > j)，它們滿足一下兩個條件（在紙上畫出來更容易明白）：

1、 k != q;

2、 i - j == k - q 或者 i - j == q -k （由題意得）

為了保證，k != q, 這里聲明并初始化數(shù)組list，使得 list[i] = i。然后隨機(jī)打亂數(shù)組，然后檢查是否滿足條件2

復(fù)制代碼代碼如下:

// 創(chuàng)建并初始化數(shù)組    
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
    list[i] = i;
// 隨機(jī)打亂數(shù)組
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 的代碼主體如下

復(fù)制代碼代碼如下:

// 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 要求求出所有有效的八皇后布局，隨機(jī)打亂數(shù)組的方法已經(jīng)不再適用，只好尋求一個可以遍歷所有可能的方法。一個最直接的方法是，使用八層 for循環(huán)，不過代碼量太大，而且腦袋容易暈掉，所以不采用這個方法。

仔細(xì)觀察Part 1中數(shù)組的值，可以發(fā)現(xiàn)，它們都在0-7之間，因此使用八進(jìn)制int數(shù)進(jìn)行遍歷可以保證包含每一個排列。由于八位數(shù)字各不相同，因此可能的排列有 8! = 40320種，而八進(jìn)制數(shù)總共有 8^8 = 16777216個，因此可能的比例占 40320/16777216 = 1/416，得到的這40320個排列還要進(jìn)行檢查才能篩選出最終有效的布局。這個方法效率還是有點(diǎn)低，不過暫且還沒有想出更高效的。

復(fù)制代碼代碼如下:

// 6.22 游戲：多種八皇后問題的解決方案(利用int值遞增，然后將其轉(zhuǎn)變?yōu)榘诉M(jìn)制字符串，再進(jìn)行檢查）
    public static void solveEightQueensMethod(){
        int start = 001234567;  // 八進(jìn)制
        int end = 076543210;   // 八進(jìn)制
        int count = 0;   // 計算有效的布局?jǐn)?shù)
        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);  // 輸出有效的布局?jǐn)?shù)
    }
// 檢查 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;
    }