برای برنامه n وزیر که کل فضای حالت رو در نظر بگیره کسی میتونه راهنمایی کنه؟

[mnsh87]

در واقع برنامه ای میخام که بهینه نباشه
و کل فضای حالت رو در نظر بگیره

[SAASTN]

درست متوجه نمی شم.
اگه منظورت تولید کل فضای حالاته باید از backtrack استفاده کنی.

[qwerty11]

8 تا حلقه ی for از صفر تا 8 بزار. حالا عددی که حلقه ی i ام نشون میده رو برابر وزیری که تو سطر i ام قرار داره فرض کن. بعدش فقط کافیه یه تابع چک بنویسی تا ببینی اینا همدیگه رو تهدید میکنن یا نه. البته به جای 8 تا حلقه میتونی از تابع بازگشتی هم استفاده کنی.
این جوابی که من دادم مربوط میشه به حالتی که میدونیم تو هر سطر قراره یه وزیر قرار بگیره. اما اگه میخواین دقیقاً تمام فضای حالت چک بشه باید تمام زیرمجموعه های 8 عضوی یه مجموعه 64 عضوی رو پیدا کنین و ...

[mnsh87]

خوب داستان اینه که برای n وزیر باید جواب بده نه 8 وزیر

[SAASTN]

همونطور که qwerty11 یک تابع بازگشتی می تونه n وزیر رو حل کنه.
یک تابع با سه پارامتر :"حداکثر سطوح" (همان n) و "سطح فعلی" و "پاسخ تشکیل شده تا این سطح" (که یک ماترسی n*n هست).
در هر بار اجرای این تابع بر اساس "پاسخ تسکیل شده تا این سطح" و ایجاد سطح بعدی با n روش، n فرزند جدید برای درخت فضای حالات ایجاد می شود و همین تابع n بار با پارامترهای : "حداکثر سطوح" (بدون تغییر)، "سطح فعلی+1" و هر یک از فرزندان تشکیل شده فراخوانی می شود. در این تابع درصورتی که "حداکثر سطوح" با "سطح فعال" برابر باشد یکی از برگ های درخت فضای حالات در پارامتر "پاسخ تشکیل شده تا این سطح" قرار دارد. آن را لیست جواب ها قرار داده و BackTrack می کنیم.
موفق باشید

[مصطفی ساتکی]

دوستان عزیز روش Backtracking یکی از روش های ضعیف تو حل این دسته مسائله مخصوص اگر مسئله فوق رو یخواهیم برای n وزیر تعمیم بدیم n رو بالا در نظر بگیرد با pc حل مسئله چنیدن سال طول میکشه.تنها راه حل سریع اینه که از GA(Genetic Algorithm) استفاده کنید. زیاد هم مشکل نیست

[SAASTN]

روش Backtracking یکی از روش های ضعیف تو حل این دسته مسائله
درست می فرمایید. ولی دوستومون از همون اول گفتند نیازی به بهینه بودن نیست و کل فضای حالات باید تشکیل بشه. backtrack هم الگوریتمیه که با حوصله لایتناهیش کل فضای حالات رو ایجاد می کنه. حالا اگه فضای حالات خیلی عظیمه دیگه کاریش نمیشه کرد.
البته در مورد همین مسئله خاص هم روش هایی هست که توی خود backtrack خیلی از حالات مردود هیچ وقت بوجود نیان و الگوریتم سریعتر عمل کنه.

[SAASTN]

سلام
یک تابع بازگشتی برای n وزیر نوشتم
procedure NQueen(const n, Level: Integer; const CurrentBoard: TBoard;
const CheckState: Boolean; const CurrentState: TColumnState;
var AllBoards: TBoardsAry);
var
I: Integer;
NewBoard: TBoard;
NewState: TColumnState;
begin
if Level=n-1 then
begin
SetLength(AllBoards, Length(AllBoards)+1);
AllBoards[Length(AllBoards)-1]:=Copy(CurrentBoard);
end
else
for I := 0 to n - 1 do
if (not CheckState) or (not CurrentState[I]) then
begin
NewBoard:=CopyBoard(n, CurrentBoard);
NewState:=Copy(CurrentState);
NewBoard[Level+1, I]:=True;
NewState[I]:=True;
NQueen(n, Level+1, NewBoard, CheckState, NewState, AllBoards);
end;
end;

در مورد همه پارامتر ها توی پست 5 توضیح دادم. غیر از CheckState که اگر true باشه الگوریتم حالاتی که در یک ستون بیش از یک وزیر باشه رو تولید نمی کنه و CurrentState که ستون های اشغال شده رو مشخص می کنه.
یه برنامه هم که کل فضای حالات رو بر اساس n نمایش میده گذاشتم.