參考
小白帶你學(xué)--回溯算法
LeetCode--回溯法心得
GitHub 標(biāo)星 15K套腹，這個牛逼開源項目讓算法真的動了起來
搜索&回溯——N皇后（hdu2553）

一、八皇后問題

八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后（棋子），使其不能互相攻擊若债，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。PS：皇后可以攻擊同一行劲装、同一列、左上左下右上右下四個方向的任意單位荐健。

問題簡化：下面我們將八皇后問題轉(zhuǎn)化為四皇后問題酱畅，并用回溯法來找到它的解

1.嘗試先放置第一枚皇后，被涂黑的地方是不能放皇后

image.png

2.第二行的皇后只能放在第三格或第四格江场，比方我們放第三格纺酸，則：

image.png

此時我們也能理解為什么叫皇后問題了，皇后旁邊容不下其他皇后址否。而在同一個房間放下四個皇后確實是個不容易的問題餐蔬。

3.step3

可以看到再難以放下第三個皇后，此時我們就要用到回溯算法了佑附。我們把第二個皇后更改位置樊诺，此時我們能放下第三枚皇后了。

image.png

4.step4

雖然是能放置第三個皇后音同，但是第四個皇后又無路可走了词爬。返回上層調(diào)用（3號皇后），而3號也別無可去权均，繼續(xù)回溯上層調(diào)用（2號）顿膨，2號已然無路可去，繼續(xù)回溯上層（1號）叽赊，于是1號皇后改變位置如下恋沃，繼續(xù)回溯。

image.png

這就是回溯算法的精髓必指，雖然沒有最終把問題解決囊咏，但是可以劇透一波，就是根據(jù)這個算法塔橡，最終能夠把四位皇后放在4x4的棋盤里梅割。也能用同樣的方法解決了八皇后問題。

image.png

二葛家、Algorithm Visualizer

一個名為Algorithm Visualizer(GitHub地址 )的直觀的算法可視化工具炮捧，在里面你可以自由選擇自己想學(xué)習(xí)的算法，每個算法它都清晰描繪了其原理和運作過程惦银。
在演示地址中咆课，找到Backtracking中的N_quenes problem末誓，核心代碼如下：

// import visualization libraries {
const { Tracer, Array2DTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer');
// }

const N = 4; // just change the value of N and the visuals will reflect the configuration!
const board = (function createArray(N) {
  const result = [];
  for (let i = 0; i < N; i++) {
    result[i] = Array(...Array(N)).map(Number.prototype.valueOf, 0);
  }
  return result;
}(N));
const queens = (function qSetup(N) {
  const result = [];
  for (let i = 0; i < N; i++) {
    result[i] = [-1, -1];
  }
  return result;
}(N));

// define tracer variables {
const boardTracer = new Array2DTracer('Board');
const queenTracer = new Array2DTracer('Queen Positions');
const logger = new LogTracer('Progress');
Layout.setRoot(new VerticalLayout([boardTracer, queenTracer, logger]));

boardTracer.set(board);
queenTracer.set(queens);
logger.println(`N Queens: ${N}X${N}matrix, ${N} queens`);
Tracer.delay();
// }

function validState(row, col, currentQueen) {
  for (let q = 0; q < currentQueen; q++) {
    const currentQ = queens[q];
    if (row === currentQ[0] || col === currentQ[1] || (Math.abs(currentQ[0] - row) === Math.abs(currentQ[1] - col))) {
      return false;
    }
  }
  return true;
}

function nQ(currentQueen, currentCol) {
  // logger {
  logger.println(`Starting new iteration of nQueens () with currentQueen = ${currentQueen} & currentCol = ${currentCol}`);
  logger.println('------------------------------------------------------------------');
  // }
  if (currentQueen >= N) {
    // logger {
    logger.println('The recursion has BOTTOMED OUT. All queens have been placed successfully');
    // }
    return true;
  }

  let found = false;
  let row = 0;
  while ((row < N) && (!found)) {
    // visualize {
    boardTracer.select(row, currentCol);
    Tracer.delay();
    logger.println(`Trying queen ${currentQueen} at row ${row} & col ${currentCol}`);
    // }
    
    if (validState(row, currentCol, currentQueen)) {
      queens[currentQueen][0] = row;
      queens[currentQueen][1] = currentCol;

      // visualize {
      queenTracer.patch(currentQueen, 0, row);
      Tracer.delay();
      queenTracer.patch(currentQueen, 1, currentCol);
      Tracer.delay();
      queenTracer.depatch(currentQueen, 0);
      Tracer.delay();
      queenTracer.depatch(currentQueen, 1);
      Tracer.delay();
      // }
      
      found = nQ(currentQueen + 1, currentCol + 1);
    }

    if (!found) {
      // visualize {
      boardTracer.deselect(row, currentCol);
      Tracer.delay();
      logger.println(`row ${row} & col ${currentCol} didn't work out. Going down`);
      // }
    }
    row++;
  }

  return found;
}

// logger {
logger.println('Starting execution');
// }
nQ(0, 0);
// logger {
logger.println('DONE');
// }

可以使用右上角的單步調(diào)試，觀察運行規(guī)律书蚪。代碼分析如下：
1.queens存放最終答案喇澡，是一個二維數(shù)組，第一維等于皇后個數(shù)N殊校，第二維是個坐標(biāo)點[第幾行晴玖，第幾列]，初始化全是默認(rèn)值-1

2.循環(huán)向queens塞入結(jié)果時为流，currentQueen表示當(dāng)前在操作哪個坐標(biāo)呕屎，對應(yīng)的是第一維，可以取出來一個坐標(biāo)值敬察。

3.起始是nQ(0,0)秀睛，對應(yīng)的是function nQ(currentQueen, currentCol)。也就是從queens的索引0開始寫入莲祸，并且currentCol是從0列開始的蹂安。nQ的意思就是newQueen，會有日志輸出

logger.println(`Starting new iteration of nQueens () with...

4.剛開始運行時锐帜，把第一個皇后放在0,0成功后田盈，緊接著就進(jìn)入它的子分支found = nQ(currentQueen + 1, currentCol + 1);。在這個子分支中缴阎，會去查第二個皇后的位置允瞧，并且currentCol加1，也就是說蛮拔，之前的列已經(jīng)不用檢查能不能放了述暂。可以理解為语泽，之前的選擇都存在queens里了，后面的選擇只是它們的子分支视卢。然后在這一列里踱卵，每一行都要做檢查，所以每次row=0据过，然后While循環(huán)中判斷row<N就一直執(zhí)行惋砂，也就是小于總行數(shù)N的意思。

5.什么時候結(jié)束绳锅？其實每個分支在遇到新的分支后西饵，都會往下走，不滿足最終條件的都相當(dāng)于剪枝了鳞芙。比如第一個皇后放在0,0時眷柔。檢查所有子分支期虾，都不符合要求。就會進(jìn)行row++驯嘱，也就是把第一個皇后放在1镶苞，0位置，繼續(xù)查子分支鞠评。

6.檢查條件

function validState(row, col, currentQueen) {
  for (let q = 0; q < currentQueen; q++) {
    const currentQ = queens[q];
    if (row === currentQ[0] || col === currentQ[1] || 
    (Math.abs(currentQ[0] - row) === Math.abs(currentQ[1] - col))) {
      return false;
    }
  }
  return true;
}

檢查一個位置能不能放茂蚓，傳入了坐標(biāo)row,col。然后把queens之前的坐標(biāo)都拿出來遍歷一下剃幌，其中斜線不能使用聋涨，用了Math.abs很方便，即一個點的左上负乡，右上牍白，左下，右下里敬鬓，單位長度距離1個單位的淹朋，都算符合條件。

7.出口
這個語句其實挺好寫的钉答，一般也就2-3行代碼础芍，大多數(shù)人都能想出來。但我覺得大多數(shù)人苦惱的就是不知道該把它放在哪兒数尿，我剛開始也是這樣仑性，后面總結(jié)了2-3題之后，我發(fā)現(xiàn)了一個萬能規(guī)律右蹦，就是把出口語句放在遞歸函數(shù)的第一行诊杆。最主要的就是不能把出口語句放在for和while循環(huán)語句里面，因為出口語句一定要方便整個函數(shù)退出

  if (currentQueen >= N) {
    // logger {
    logger.println('The recursion has BOTTOMED OUT. All queens have been placed successfully');
    // }
    return true;
  }

8.遞歸函數(shù)的參數(shù)
這個遞歸函數(shù)的參數(shù)的設(shè)置也是有很大門道的何陆，設(shè)置的好就很容易得到答案晨汹，否則弄大半天可能還是沒有一點反應(yīng)。大家一定要記住一點：這個參數(shù)是隨著每一次的遞歸操作而發(fā)生改變的贷盲。而回溯法很關(guān)鍵的一點就是：如果當(dāng)前操作行不通淘这，如何回溯到上一步操作。大家繼續(xù)看上面貼的兩個遞歸函數(shù)的參數(shù)巩剖，會發(fā)現(xiàn)其參數(shù)都是要改變的铝穷，既然參數(shù)會發(fā)生改變，那么我們要如何保存其上一步操作的值呢佳魔？大家可以再細(xì)細(xì)看看上述兩個函數(shù)的傳值操作曙聂。

for index in range(nums):
    Flag = conflict(queen_str, index)
    # 如果當(dāng)前位置的皇后是否與之前所有位置的皇后沒有沖突，則執(zhí)行下述代碼
    if Flag is False:
       back(queen_str+str(index))

大家可以看到back(queen_str+str(index))這一步鞠鲜，其傳的參數(shù)就是queen_str+str(index) 其實想法就是不破壞當(dāng)前參數(shù)的值宁脊，直接把當(dāng)前值加上一個值(大家可以理解為定義了另一個非queen_str當(dāng)前值的值給傳到下一次函數(shù))断国，只要不破壞當(dāng)前值，函數(shù)就能回溯朦佩。這一步很關(guān)鍵并思，大家可以好好品味。

for index in range(nums):
    Flag = conflict(queen_str, index)
    # 如果當(dāng)前位置的皇后是否與之前所有位置的皇后沒有沖突语稠，則執(zhí)行下述代碼
    if Flag is False:
       queen_str = queen_str+str(index)
       back(queen_str )

如果大家還有些疑惑的話宋彼，可以再把傳值操作改成這樣試試，你會發(fā)現(xiàn)結(jié)果會大相徑庭的仙畦，這里就是破壞了當(dāng)前值输涕。

關(guān)于參數(shù)，我還有一點就是強(qiáng)調(diào)：就是結(jié)果一定是要有一個全局參數(shù)來保存慨畸，這個全局參數(shù)不會隨著每一次的遞歸操作而隨時改變莱坎，它只是用來保存每一次遞歸操作成功時的結(jié)果，其它的不關(guān)它的事寸士。你仔細(xì)看看這兩個程序也會發(fā)現(xiàn)：它們在一開始就定義了一個List空列表檐什。

9.遞歸函數(shù)的處理過程
這個過程是最關(guān)鍵的了，但是也很少有人能把它說清楚弱卡，當(dāng)然也包括我乃正。我想來想去，總結(jié)起來一句話就是：如果當(dāng)前遞歸過程的處理參數(shù)符合要求婶博，則執(zhí)行相關(guān)賦值或其它操作瓮具，然后轉(zhuǎn)入下一次遞歸，如果下一次遞歸不能找到出口凡人，則把之前相關(guān)賦值或其它操作重置為初始狀態(tài)名党。

迷宮問題的處理過程

nums[pos_x, pos_y] = 0
back(next_position, pos_list_copy)
# 如果沒有找到出口，則將當(dāng)前上一個位置0重置為1挠轴，回溯
nums[pos_x, pos_y] = 1

三传睹、回溯算法套路詳解

回溯算法的框架：

result = []
def backtrack(路徑, 選擇列表):
    if 滿足結(jié)束條件:
        result.add(路徑)
        return

    for 選擇 in 選擇列表:
        做選擇
        backtrack(路徑, 選擇列表)
        撤銷選擇

其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」岸晦，在遞歸調(diào)用之后「撤銷選擇」欧啤，特別簡單。

請問一下委煤，遞歸之后為何要撤銷選擇堂油？
因為在遞歸之前已經(jīng)從選擇列表中對當(dāng)前節(jié)點做出了一個選擇修档，改變了當(dāng)前節(jié)點的路徑和選擇列表碧绞。因此如果想要從選擇列表中對當(dāng)前節(jié)點做另一個選擇，就需要先把前一個選擇對路徑和選擇列表的影響消除掉吱窝，讓路徑和選擇列表回到?jīng)]有做選擇的狀態(tài)讥邻，因此需要把前一個節(jié)點從路徑中消除迫靖，并重新添加到選擇列表中。

vector<vector<string>> res;

/* 輸入棋盤邊長 n兴使，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
    // '.' 表示空系宜，'Q' 表示皇后，初始化空棋盤发魄。
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
}

// 路徑：board 中小于 row 的那些行都已經(jīng)成功放置了皇后
// 選擇列表：第 row 行的所有列都是放置皇后的選擇
// 結(jié)束條件：row 超過 board 的最后一行
void backtrack(vector<string>& board, int row) {
    // 觸發(fā)結(jié)束條件
    if (row == board.size()) {
        res.push_back(board);
        return;
    }

    int n = board[row].size();
    for (int col = 0; col < n; col++) {
        // 排除不合法選擇
        if (!isValid(board, row, col)) 
            continue;
        // 做選擇
        board[row][col] = 'Q';
        // 進(jìn)入下一行決策
        backtrack(board, row + 1);
        // 撤銷選擇
        board[row][col] = '.';
    }
}

/* 是否可以在 board[row][col] 放置皇后盹牧？ */
bool isValid(vector<string>& board, int row, int col) {
    int n = board.size();
    // 檢查列是否有皇后互相沖突
    for (int i = 0; i < n; i++) {
        if (board[i][col] == 'Q')
            return false;
    }
    // 檢查右上方是否有皇后互相沖突
    for (int i = row - 1, j = col + 1; 
            i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q')
            return false;
    }
    // 檢查左上方是否有皇后互相沖突
    for (int i = row - 1, j = col - 1;
            i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q')
            return false;
    }
    return true;
}

四、參考 劍指OFFER

回溯法可以看成是蠻力法的升級版励幼，它從解決問題每一步的所有可能選項里系統(tǒng)的選擇出一個可行的解決方案汰寓。回溯法非常適合由多個步驟組成的問題苹粟，并且每個步驟都有多個選項有滑。當(dāng)我們在某一步選擇了其中一個選項時，就進(jìn)入下一步嵌削，然后面臨新的選項毛好。我們就這么重復(fù)選擇，直至到達(dá)最終的狀態(tài)苛秕。
　　用回溯法解決的問題的所有選項可以形象地用樹狀結(jié)構(gòu)表示肌访。在某一步有n個可能的選項，那么該步驟可以看成是樹狀結(jié)構(gòu)中的一個節(jié)點想帅，每個選項看成樹中節(jié)點的連接線场靴，經(jīng)過這些連接線到達(dá)某個節(jié)點的n個子節(jié)點。樹的葉節(jié)點對應(yīng)著終結(jié)狀態(tài)港准。如果在葉節(jié)點的狀態(tài)滿足題目的約束條件旨剥，那么我們找到了一個可行的解決方案。
　　如果在葉節(jié)點的狀態(tài)不滿足約束條件浅缸，那么只好回溯到它的上一個節(jié)點再嘗試其他選項轨帜。如果上一個節(jié)點所有可能的選項都已經(jīng)試過，并且不能達(dá)到滿足約束條件的終結(jié)狀態(tài)衩椒，則再次回溯到上一個節(jié)點蚌父。如果所有節(jié)點的所有選項都已經(jīng)嘗試過仍然不能到達(dá)滿足約束條件的終結(jié)狀態(tài)，則該問題無解毛萌。

如果面試題要求在二維數(shù)組(可能具體表現(xiàn)為迷宮或棋盤)上搜索路徑苟弛，那么我們可以嘗試用回溯法。通掣蠼回溯法很適合用遞歸的代碼實現(xiàn)膏秫。只有當(dāng)面試官限定不可以用遞歸實現(xiàn)的時候，我們再考慮用棧來模擬遞歸的過程做盅。