نمونه سورس کد حل مسئله N-Queen با DFS و BFS در سی شارپ
در این مقاله به طور کامل و جامع به توضیح روش‌های DFS و BFS برای مسئله N-Queen می‌پردازیم و نحوه نمایش نتیجه در سی شارپ را توضیح می‌دهیم. برای هر دو رویکرد، ابتدا مفهوم پایه را بیان می‌کنیم، سپس ساختار داده‌ها را توضیح می‌دهیم و در نهایت نکات پیاده‌سازی کلیدی را بررسی می‌کنیم. هدف این است که بتوانید با داشتن این توضیحات، کد کامل یا شبه‌کد قابل اجرا بنویسید و نتیجه را به شکل گرافیکی یا متنی نمایش دهید.
چارچوب اصلی مسئله N-Queen چیست؟
هدف این است که نوزده‌ها یا N تا شاه در یک صفحه n×n قرار بگیرند بدون اینکه در ردیف، ستون یا قطرها برخوردی داشته باشند.
برای یک rدیف از روش DFS یا BFS، باید در هر گام یک ستون مناسب در هر ردیف را بیابید و از طریق backtracking یا گسترش گره‌ها جلو رفت.
نمایش نتیجه معمولاً به صورت فهرست ردیف به ردیف یا آرایه‌ای از ستون‌های شاها در هر ردیف انجام می‌شود.
روش DFS با بازگشتی یا Backtracking
مفهوم پایه: در هر گام، برای ردیف فعلی، تمام ستون‌های معتبر را بررسی می‌کنیم. اگر ستونی مناسب یافتیم، شاه را قرار می‌دهیم و به ردیف بعدی می‌رویم. اگر به بن‌بست رسیدیم، به گام قبل برمی‌گردیم تا گزینه دیگری را امتحان کنیم.
داده‌های اصلی: یک آرایه یا لیست که شاها را در ستون‌های مختلف ردیف‌های قبلی نشان می‌دهد. معمولاً از یک آرایه int[colCount] استفاده می‌کنیم که مقدار هر اندیس نشان‌دهنده ستونی است که شاه در آن ردیف قرار دارد.
ارزیابی برخوردها: برای هر گام باید سه منطق بررسی کنیم: همان ستون، همان شیاه در ستون‌های قبل و تشابه قطری diagonal. معمولاً با استفاده از سه مجموعه یا آرایه boolean چک می‌کنیم که آیا ستون یا قطر قبلاً استفاده شده است.
پیاده‌سازی پایه: تابع بازگشتی Solve(row) که اگر row == N، یک راه‌حل پیدا شده است و آن را ذخیره می‌کند. در غیر این صورت، برای هر ستون از 0 تا N-1، اگر جایگاه امن است، حلقه را ادامه می‌دهد و دوباره Solve(row+1) را فراخوانی می‌کند.
نمایش نتیجه: پس از یافتن هر راه‌حل، آرایه شاه‌ها را چاپ می‌کنیم یا به یک ساختار گرافیکی ارسال می‌کنیم. در سی شارپ می‌توانید ماتریس یا لیست از مختصات را چاپ کنید.
روش BFS با استفاده از صف
تفاوت اصلی با DFS: به جای بازگشتی بودن، ...
