Backtracking 是一種演算法的策略，可用來解決三種面向的問題，分別是 Decision problem, Optimization problem, 以及 Enumeration problem．有關 Optimization problem 在前面的文章裡已經談過不少，這裡不多說明．一個 Decision problem 可能會有至少一個或一個以上的解答，這種問題我們通常只要找一個可用的解答．Enumeration problem 和 Optimization problem 蠻相近，就是要將所有解答找出來．舉個例子，之前講過的老鼠走迷宮是一種問題，如果我們要找一條可行的路，那麼老鼠走迷宮將是 Decision problem．如果我們要找出一條最短的路，此時便是 Optimization problem．如果要將所有可行的路找出來，這便是 Enumeration problem．不同的問題需要不同的解決策略．Backtracking 就這麼巧地可以用來做為這三種問題的解決策略．
以西洋棋裡 n-Queen 問題來說明，一般以 n = 8 為市面上較為熱門的題目，現在我們把 input size 縮小一點，將 n=4. 而棋盤和其中一個可行的解答如下:
Source: https://www.geeksforgeeks.org/backtracking-introduction/
n-Queen 問題的解決策略如果用最直覺的暴力法來做，其解法如下
1. 列出所有 Queen 的排列座標，例如
Answer candidate 1: (0,0) (0,1) (0,2) (0,3)
Answer candidate 2: (0,0) (0,1) (0,2) (1,3)
Answer candidate 3: (0,0) (0,1) (0,2) (2,3)
Answer candidate 4: (0,0) (0,1) (0,2) (3,3)
Answer candidate 5: (0,0) (0,1) (1,2) (0,3)
.... 以此類推， 一共有 4x4x4x4 = 256 種位置．
2. 然後將每一個候選答案放到一個檢查器．這個檢查器就是題目要求的，要讓每個皇后所在的位置不會影響到其他的皇后．這個檢查器要執行的程式碼就是問題本身所給出的限制．你我都知道，暴力法簡單粗暴，保證一定讓你能找到答案，但不保證能快速找到答案．這個問題的 "限制" 本身就是一個有點複雜的運算了．如果你忘了西洋棋的皇后走法，你需要複習一下才能知道這裡所說有點複雜運算的意思了．
如果是用 Backtracking 的策略，該怎麼做呢 ?
Backtracking 的策略在我看來和暴力法是有一點接近的．只是差別在於 Backtracking 不會一開始將所有可能列出來，然後再進行對每個輸入一一地檢查．Backtracking 的策略是在產生所有可能的排序方式過程中，就直接檢查了．如果在過程中不符合 "限制" 時，則中斷這條路，然後跳到下一組排列來做.
以上述的答案候選為例子:
一開始，第一個皇后放在 (0,0)，然後試著將第二個皇后放在 (0,1)，執行檢查器，這樣檢查器會回傳 false，因為棋盤上同一行只能有一個皇后．於是，後面答案候選裡面只要是 (0,0) (0,1) 開頭的組合便可跳過．前面兩個皇后的位置已經不合法了，所以後面的皇后也不用浪費時間檢查．若以程式的角度來看，某一層次的 for loop 將可以整個跳過去而不執行．所以，下一個要檢查的便是從 (0,0) (1,1) 開頭的答案.
以上的過程的解題思考就是 Backtracking．
看到這裡，雖然我們沒有寫出細節的程式碼，但我相信你能感受到 Backtracking 的解題策略的精神是什麼了．Backtracking 適合用在需要 recursion 來解決的問題．在我們試著將所有的可能答案窮舉出來的過程中，就執行著 "檢查器"，一旦發現檢查器不通過，就直接跳開這一個層次的答案，直接轉往下一個層次，這就是 Backtracking 能夠省出時間的方式．上述的 n-Queen 是一個常見的例子，Sudoku 也是一個常見的例子. 我相信在你的工作中 Backtracking 能派上用場的時機點是很多的．
底下的程式碼是我小徒弟在數個月前練習解決 Sudoku 題目的程式碼，其解決策略是 Backtracking.
