حل مسئله N-Queens با الگوریتم بازگشتی + پیاده‌سازی در پایتون 👑🐍

مسئله N-Queens یک معمای کلاسیک در علوم کامپیوتر است که هدف آن قرار دادن N مهره شاه روی یک صفحه شطرنج N×N است، به طوری که هیچ دو مهره‌ای یکدیگر را تهدید نکنند. این مسئله نمونه‌ای عالی برای یادگیری الگوریتم‌های بازگشتی و پشته است.

🎯 روش حل بازگشتی (Backtracking)

الگوریتم بازگشتی برای حل این مسئله به این صورت عمل می‌کند:

ستون به ستون پیش می‌رود و سعی می‌کند ملکه را در یک سطر قرار دهد.
اگر جایگذاری امن بود (یعنی با ملکه‌های قبلی تداخل نداشت)، به ستون بعدی می‌رود.
اگر به بن‌بست رسید، به مرحله قبل بازمی‌گردد (Backtrack) و جایگاه ملکه را تغییر می‌دهد.

✅ بررسی شرایط ایمن بودن قرارگیری ملکه

یک ملکه در موقعیت (row, col) امن است اگر:

در سطر مشابه ملکه دیگری نباشد.
در قطر اصلی (\) ملکه دیگری نباشد.
در قطر فرعی (/) ملکه دیگری نباشد.

👩‍💻 پیاده‌سازی در پایتون

python


def solve_n_queens(n):
    def is_safe(board, row, col):
        # بررسی سطر سمت چپ
        for i in range(col):
            if board[row][i] == 1:
                return False
        
        # بررسی قطر بالا سمت چپ
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        # بررسی قطر پایین سمت چپ
        for i, j in zip(range(row, n, 1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        return True

    def backtrack(col):
        if col >= n:
            solutions.append([row[:] for row in board])
            return
        
        for row in range(n):
            if is_safe(board, row, col):
                board[row][col] = 1
                backtrack(col + 1)
                board[row][col] = 0  # Backtrack

    board = [[0] * n for _ in range(n)]
    solutions = []
    backtrack(0)
    return solutions

# مثال برای صفحه 4x4
n = 4
solutions = solve_n_queens(n)
for sol in solutions:
    for row in sol:
        print(" ".join("Q" if x else "." for x in row))
    print()

خروجی برای N=4:


. . Q .
Q . . .
. . . Q
. Q . .

. Q . .
. . . Q
Q . . .
. . Q .

⚡ بهینه‌سازی الگوریتم

استفاده از مجموعه‌ها (Sets) برای پیگیری سطرها و قطرهای اشغال‌شده.
محدود کردن جستجو با تقارن‌های صفحه شطرنج.
استفاده از روش‌های هیوریستیک برای Nهای بزرگ.

🎯 کاربردهای مسئله N-Queens

آزمایش الگوریتم‌های بازگشتی
بهینه‌سازی مسیریابی
طراحی مدارهای الکترونیکی

💡 نتیجه‌گیری

حل مسئله N-Queens یک تمرین عالی برای درک الگوریتم‌های بازگشتی و Backtracking است. پیاده‌سازی آن در پایتون نیز به درک بهتر مفاهیم پشته و شرط‌های بازگشت کمک می‌کند.

🎯 شما چه راه‌حل دیگری برای این مسئله سراغ دارید؟ نظراتتان را با ما به اشتراک بگذارید! 👇💬