python求解八皇后問題中的回溯究竟體現在哪裡了？

這是摘自Python基礎教程中八皇后問題中的代碼。確實能解決問題，但是我實在是不理解回溯體現在哪裡。也就是說，比如在某次迭代中，發現這次要放置的皇后所有可能的位置都和之前的皇后衝突（用conflict()判斷），那麼理應回溯，但是代碼中哪裡實現了這個功能？

我是初學者，對遞歸和回溯還很頭疼，麻煩大神們講清晰一點哦～～

---

這裡的回溯是用遞歸實現的，而且巧妙地使用到了yield。

——————————————————————————————————————

回溯法的思路很簡單，其實就是模擬我們使用大腦來求解這一問題。所以回溯法的代碼其實很簡單。以num=4為例，其代碼應該就是

def queens0(num=4):
for i in range(num):
if not conflict([], i):
for j in range(num):
if not conflict([i], j):
for k in range(num):
if not conflict([i,j],k):
for m in range(num):
if not conflict([i,j,k],m):
print ([i,j,k,m])


那麼上面的代碼的回溯在哪裡呢？其實就是某一層的嵌套循環結束之後，就返回上一層繼續循環。這就是最本質的回溯。

但是沒有人會這樣來寫八皇后的代碼，num=4時，要書寫4個循環，num=8時要書寫8個循環，如果num是一個變數，運行時才確定大小，那都沒辦法寫了。

估計題主所想的回溯就是使用一個while循環，外加一個保存處理到第幾行的n所實現的回溯演算法，這種演算法裡面，有n=n-1這一明顯的回溯過程。但題主代碼裡面是用遞歸層次的摺疊來實現的。遞歸的思路和前面queens0函數的思路是一樣的。如果你把代碼簡單地展開看看

def queens(num=8, state=()):
for pos in range(num):
if not conflict((), pos):
queens(num, state+(pos,)) #遞歸調用，將此行展開
# 展開之後
def queens(num=8, state=()):
for pos in range(num):
if not conflict(state, pos):
#下面的就是展開的代碼
for pos2 in range(num):
if not conflict((pos,), pos2):
# 下面又可以展開了
queens(num, state+(pos,))
...


這個展開到len(state)==num-1為止，也就是說下面要展開num-1次。

第一次for循環的時候len(state)=0，也就是說完全展開共有8個for循環。因此實際展開的代碼，就是queens0類似的代碼。

---

推薦閱讀：