問(wèn)題介紹

摘自百度百科
八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型案例。該問(wèn)題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊部服，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上拗慨，問(wèn)有多少種擺法廓八？

回溯法

概念

摘自百度百科
回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法赵抢，按選優(yōu)條件向前搜索剧蹂，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)烦却，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)宠叼，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”冒冬。

思想

在回溯法中伸蚯，每次擴(kuò)大當(dāng)前部分解時(shí)，都面臨一個(gè)可選的狀態(tài)集合简烤，新的部分解就通過(guò)在該集合中選擇構(gòu)造而成剂邮。這樣的狀態(tài)集合，其結(jié)構(gòu)是一棵多叉樹横侦，每個(gè)樹結(jié)點(diǎn)代表一個(gè)可能的部分解挥萌，它的兒子是在它的基礎(chǔ)上生成的其他部分解。樹根為初始狀態(tài)枉侧，這樣的狀態(tài)集合稱為狀態(tài)空間樹引瀑。
回溯法對(duì)任一解的生成，一般都采用逐步擴(kuò)大解的方式榨馁。每前進(jìn)一步憨栽，都試圖在當(dāng)前部分解的基礎(chǔ)上擴(kuò)大該部分解。它在問(wèn)題的狀態(tài)空間樹中辆影，從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)徒像，以深度優(yōu)先搜索整個(gè)狀態(tài)空間黍特。這個(gè)開始結(jié)點(diǎn)成為活結(jié)點(diǎn)蛙讥，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處灭衷，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)次慢。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)翔曲。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)迫像，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)瞳遍，應(yīng)往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)處闻妓，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)÷有担回溯法以這種工作方式遞歸地在狀態(tài)空間中搜索由缆，直到找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)時(shí)為止。

四皇后問(wèn)題回溯模型

解題框架

對(duì)于回溯法的求解模型一般有兩種猾蒂，遞歸解法及非遞歸解法均唉。

非遞歸法

List result, i;
init(result, n);//初始化解結(jié)果
i = 1;
while (i>0)
{
  if(i > n) {   
      //搜索到一個(gè)解，輸出肚菠；
      //回溯
      i--;
  }
  else { 
        set(result, i, j);//賦初值或嘗試下一個(gè)值
        for (j = 下界; j <= 上界; j++) {
             if (constaint(result, j)) {
                break;
             }
        }
        if(滿足條件)
        {
             i = i + 1;
        }
        else {
            清理所占的狀態(tài)空間舔箭；            
            // 回溯
            i = i – 1; 
        }
}

遞歸法

void backTrace(int i) {
    if(i == 1) {
        init(result, n);
    }
    if(i > n) {
        //找到一個(gè)解，輸出
    } else {
        for (int j = 下界; j <= 上界; j++) {
            set(result, i, j);
            if(constraint(r, i)) {
                if(i <= n) {
                    backTrace(i + 1);
                }
            }
        }
    }
}

八皇后問(wèn)題求解

class Queen {
    int n;
    List<List<Integer>> result = new ArrayList<>();

    public Queen(int n) {
        this.n = n;
    }

    boolean conflict(List<Integer> state, int x) {
        for (int i = 1; i < x; i++) {
            if (state.get(i).equals(state.get(x)) || x - i == Math.abs(state.get(x) - state.get(i))) {
                return true;
            }
        }
        return false;
    }

    void init(List<Integer> list, int size) {
        for (int i = 0; i <= size; i++) {
            list.add(0);
        }
    }

    void reInit(List<Integer> list, int size) {
        for (int i = 2; i <= size; i++) {
            list.set(i, 0);
        }
    }

    void queen() {
        int i = 1;
        List<Integer> r = new ArrayList<>(n + 1);
        init(r, n);
        while (i > 0) {
            if (i > n) {
                //找到一組解
                ArrayList<Integer> list = new ArrayList<>(r.size() - 1);
                for (int index = 1; index < r.size(); index++) {
                    list.add(r.get(index));
                }
                result.add(list);
                //找到一組解后同樣回溯
                i = i - 1;
            } else {
                //找到第i行對(duì)應(yīng)的合適的列
                int j = r.get(i);
                r.set(i, j + 1);
                for (j = r.get(i); j <= n; j++) {
                    r.set(i, j);
                    if (!conflict(r, i)) {
                        break;
                    }
                }
                if (j <= n) {
                    //找到了合適位置蚊逢，繼續(xù)下一個(gè)
                    i++;
                } else {
                    //回溯
                    r.set(i, 0);
                    i--;
                }
            }
        }
    }

    List<Integer> r = new ArrayList<>(n);
    void queenRecurse(int i) {
        if(i == 1) {
            init(r, n);
        }
        if(i > n) {
            ArrayList<Integer> list = new ArrayList<>(r.size() - 1);
            for (int index = 1; index < r.size(); index++) {
                list.add(r.get(index));
            }
            result.add(list);
        } else {
            for (int j = 1; j <= n; j++) {
                r.set(i, j);
                if(!conflict(r, i)) {
                    if(i <= n) {
                        queenRecurse(i + 1);
                    }
                }
            }
        }
    }

    void print() {
        System.out.println(n + " queen problem has " + result.size() + " results!");
        for (int i = 0; i < result.size(); i++) {
            List<Integer> list = result.get(i);
            for (Integer in : list) {
                System.out.print(in + " ");
            }
            System.out.println();
        }
    }
}