درباره N-Queens
مسئله N وزیر: N وزیر را روی صفحه N×N شطرنج قرار بده بهگونهای که هیچ وزیری وزیر دیگری را تهدید نکند. Backtracking ستونها را یکی یکی پر میکند. اگر در ستونی هیچ خانه امنی نباشد، به ستون قبل برمیگردد.
راهحلهای ۴×۴
2
راهحلهای ۵×۵
10
راهحلهای ۶×۶
4
راهحلهای ۸×۸
92
Backtracking چیست؟
امتحان میکنیم، اگر به بنبست رسیدیم برمیگردیم و مسیر دیگری امتحان میکنیم. مثل حل کردن سودوکو — جلو میرویم تا به مشکل برسیم، سپس عقبنشینی میکنیم.
n_queens.py
def n_queens(n):
solutions = []
def is_safe(queens, row, col):
for r, c in queens:
if r==row or c==col: return False
if abs(r-row)==abs(c-col): return False
return True
def solve(col, queens=[]):
if col == n:
solutions.append(queens[:])
return
for row in range(n):
if is_safe(queens, row, col):
queens.append((row, col)) # place
solve(col + 1, queens) # recurse
queens.pop() # backtrack ←
solve(0)
return solutions