مسئله N وزیر
N-Queens ProblemN-Queens باید N وزیر را روی صفحه N×N قرار دهد به‌طوری‌که هیچ دو وزیری در یک row، column یا diagonal نباشند. Backtracking انتخاب‌ها را امتحان می‌کند و به‌محض conflict مسیر را قطع می‌کند.
اول این مفهوم را در ذهن نگه دار
N-Queens باید N وزیر را روی صفحه N×N قرار دهد به‌طوری‌که هیچ دو وزیری در یک row، column یا diagonal نباشند. Backtracking انتخاب‌ها را امتحان می‌کند و به‌محض conflict مسیر را قطع می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
در هر row فقط یک وزیر قرار بده.
columnها و diagonalهای اشغال‌شده را با Set یا Bitmask نگه دار، به row بعد برو و بعد از برگشت انتخاب را undo کن.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
constraint و edge case را بازگو کن.
pattern و invariant را پیدا کن.
قبل از کد یک مثال کوچک را دستی اجرا کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مسئله N وزیر هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function solveNQueens(n) {
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
const board = Array(n).fill(-1), solutions = [];
function place(row) {
if (row === n) { solutions.push([...board]); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
cols.add(col); diag1.add(row-col); diag2.add(row+col); board[row] = col;
place(row + 1);
cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
}
}
place(0);
return solutions;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی invariant pattern با constraint مسئله هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف invariant مستقیم سراغ کد نرو.
- قبل از جواب صحیح ساده، زود optimization نکن.
مدل یک پاسخ حرفه‌ای
نکته اصلی pruning است؛ Backtracking همه boardهای کامل را کورکورانه نمی‌سازد بلکه prefixهای نامعتبر را خیلی زود حذف می‌کند.
مسئله N وزیر چه مسئله‌ای را حل می‌کند؟
N-Queens باید N وزیر را روی صفحه N×N قرار دهد به‌طوری‌که هیچ دو وزیری در یک row، column یا diagonal نباشند. Backtracking انتخاب‌ها را امتحان می‌کند و به‌محض conflict مسیر را قطع می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف invariant مستقیم سراغ کد نرو.