توضبح برنامه ‌چند وزیر n-queen به روش بازگشتی

[parsbin]

سلام
یک برنامه به روش بازگشتی به زبان c در ویکیپدیا پیدا کردم
ولی یکم برام گنگه
و نیاز به توضیح دارم
که چطوری کار میکنه

void queens ( index i)

{

index j;

if ( promising(i))

if ( i == n)

cout << col [1] through col [n];

else

for ( j = 1 ; j ? n ; j++ ) {



col [ i +1 ] = j;

queens ( i + 1);

}

}

bool promising ( index i )

{

index k ;

bool switch;

k = 1;

switch = true ;

while ( k < i && switch ) {

if (col [i] == col[k] || abs(col[i] – col[k] == i-k)

switch = false;

k++;

}

return switch;

}

[Negin.cs]

سلام

nQueen میاد بررسی میکنه تو یه صفحه شطرنج n*n ، تو چه حالتهایی میتونیم n تا وزیر رو بچینیم => void queens ( index i)

i شماره وزیر هست که میاد تو صفحه

امید بخش بودن اون وزیر رو بررسی میکنیم if ( promising(i))
اگه این شماره وزیر n امین وزیر باشه -> هرچی شماره ستون تا اینجا جمع شده که وزیرای شماره 1 تا اینجا نشستن رو بیا چاپ کن :if ( i == n)cout << col [1] through col [n];
درغیراینصورت به بررسی برای وزیرا ادامه بده

bool promising ( index i ) هم امید بخش بودن وزیر یعنی قابل قبول بودنش توی صفحه ( به بقیه کیش نده) رو بررسی میکنه که قاعدتا یعنی با وزیرهای قبلی نباید تو یه ستون : col [i] == col[k] یا حالت قطری ماتریسی یعنی حرکت فیلی : abs(col[i] – col[k] == i-k باشه

[parsbin]

main باید چه شکلی باشه؟
حلقه 64 تایی میخواد برای queens ( index i) ؟

[Negin.cs]

این در اصل شبه کد هست که باهاش الگوریتم رو میگن
واسه main فکرکنم به تعداد n بهش بدی کافی باشه
حالا باز چک کنید...

[Salar Ashgi]

عموما الگوریتم هایی که بروش عقبگرد (BackTrack) حل میشن ، یه تابعی شبیه promising دارن که میاد شرط درستی جهت حل مساله
رو در نظر می گیره . مثلا در مورد مساله 8 وزیر ، میاد بررسی میکنه که دو وزیر کی میتونن همدیگه رو تهدید کنن :

1. سطری 2. ستونی 3. قطری

البته این تابع میتونه بروش های متفاوتی پیاده سازی بشه .

یه روش حل ساده واسه n وزیر اینه که : (البته کمی order الگوریتم بالاست)

شما بیای واسه 8 وزیر همون تعداد حالات ترکیب 8 عدد یعنی !8 (هشت فاکتوریل) رو در نظری بگیری منهای

حالات غیر قابل قبول که بالا گفتم .

موفق باشید ./