N 皇后問題（N-queens problem）
在西洋棋盤上，皇后會攻擊任何與它同列、同行或同對角線的棋子。N 皇后問題問：你能在 N 乘 N 的棋盤上擺 N 個皇后，使任兩個都不互相攻擊嗎？對經典的 8 乘 8 棋盤，答案是肯定的（共有 92 個相異解），而這個謎題是回溯法的教科書範例——小到能在腦中描繪，難到盲目列舉無望。
第一個洞見大幅砍掉搜尋空間：既然任兩個皇后不能同行，那就每行恰擺一個皇后。如此一來候選解只是「替 N 行各選一個列」——一個陣列，其中第 c 項是第 c 行皇后所在的列。回溯由左到右填這個陣列：替當前這一行試每個列，遞迴之前先檢查新皇后沒有跟任何已擺好的皇后同列或同對角線（兩皇后在同一對角線上，恰當它們列的差之絕對值等於行的差之絕對值時）。若擺法安全，就遞迴到下一行；若衝突，就跳過；若沒有列可行，就返回，讓前一行去試它的下一個列。一塊填滿的棋盤（N 行全填）就是一個解。
它為何有效、又為何快：限制成每行一個，把空間從 C(N^2, N) 種棋盤擺法縮成 N^N 種列選擇，而可行性剪枝又再縮一次，因為在第 2 行偵測到的衝突，會一口氣剪掉第 3 到第 N 行的所有完成方式。解的數目成長很快（沒有已知的閉式），所以這問題也是巧妙計數的基準；但作為入門一課，它乾淨地示範了「做—遞迴—撤銷」迴圈，以及一個提早的衝突檢查如何把天文般龐大的列舉，變成筆電一眨眼就解出的東西。
對 4 皇后，把擺法表示成「每行所在的列」。試第 0 行 = 列 0、第 1 行 = 列 2（未被攻擊），第 2 行沒有安全的列（每個列都與前兩個在行或對角線上衝突），於是回溯、改第 1 行。搜尋會落到兩個解 [1,3,0,2] 與 [2,0,3,1]——讀作：第 0 行的皇后在列 1，依此類推。
每行一個皇后把問題化為一個列陣列；對每次擺法做一個對角線檢查，就完成了全部剪枝。
除了 N = 2 和 3，N 皇后對每個 N 都有解，而且找出一個很容易——但「數出全部解」依然昂貴且沒有已知的簡單公式，所以別把「容易滿足」誤當成「容易計數」。