Printable View
سلام
یک برنامه به روش بازگشتی به زبان 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;
}
سلام
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 باشه
main باید چه شکلی باشه؟
حلقه 64 تایی میخواد برای queens ( index i) ؟
این در اصل شبه کد هست که باهاش الگوریتم رو میگن
واسه main فکرکنم به تعداد n بهش بدی کافی باشه
حالا باز چک کنید...
عموما الگوریتم هایی که بروش عقبگرد (BackTrack) حل میشن ، یه تابعی شبیه promising دارن که میاد شرط درستی جهت حل مساله
رو در نظر می گیره . مثلا در مورد مساله 8 وزیر ، میاد بررسی میکنه که دو وزیر کی میتونن همدیگه رو تهدید کنن :
1. سطری 2. ستونی 3. قطری
البته این تابع میتونه بروش های متفاوتی پیاده سازی بشه .
یه روش حل ساده واسه n وزیر اینه که : (البته کمی order الگوریتم بالاست)
شما بیای واسه 8 وزیر همون تعداد حالات ترکیب 8 عدد یعنی !8 (هشت فاکتوریل) رو در نظری بگیری منهای
حالات غیر قابل قبول که بالا گفتم .
موفق باشید ./