مسئله N-Queen

N-Queen: کلاسیک‌ترین مسئله Backtracking — قرار دادن n وزیر در صفحه n×n بدون تهدید، با هرس هوشمند

مسئله

n وزیر در صفحه n×n طوری که هیچ دو وزیری همدیگر را تهدید نکنند (سطر، ستون، قطر). برای n=۸ (شطرنج کلاسیک) ۹۲ جواب وجود دارد!

مدل‌سازی هوشمند

بینش کلیدی: هر سطر دقیقاً یک وزیر دارد ← مسئله به «انتخاب ستون برای هر سطر» تبدیل می‌شود — n انتخاب، هر کدام n گزینه.

هرس — سه شرط تهدید

وزیر در (r1, c1) و (r2, c2) تهدید می‌کنند اگر:

پس فقط ستون و دو قطر را با مجموعه‌ها چک می‌کنیم — O(1) به‌جای O(n)!

الگوریتم

def backtrack(row):
    if row == n: ثبت جواب; return
    for col in range(n):
        اگر (row, col) امن است:
            قرار بده (ثبت در مجموعه‌ها)
            backtrack(row + 1)
            بردار (حذف از مجموعه‌ها)

درخت جستجو با هرس

بدون هرس: nⁿ حالت (n=8 → ۱۶ میلیون!). با هرس ستون/قطر، درخت به‌شدت کوچک می‌شود — عملاً چند هزار گره. قدرت هرس!

پیچیدگی

بدون هرس O(nⁿ)؛ با هرس، به‌طور تجربی بسیار کمتر (هیچ فرمول بسته‌ای ندارد — از جداول معروف است). حافظه: O(n) برای مجموعه‌ها + پشته.

کاربرد واقعی

N-Queen مدل مسائل قید‌محور (CSP) است: زمان‌بندی، تخصیص منابع، چیدمان مدار — هرجا «قرار دادن چیزها با قیود متقابل» دارید، همین الگو است!

نکته مصاحبه: اول راه‌حل «یک جواب» را بگویید؛ اگر پرسیدند «همه جواب‌ها»، فقط ثبت نتایج در لیست به‌جای return. تفاوت دو نسخه همین یک خط است!

جمع‌بندی

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

ابزارهای مرتبط