صفر و یک

مقدمه:

تکنیک عقبگرد که از آن برای حل مسائلی استفاده می شو که در آنها دنباله ای از اشیا از یک مجموعه مشخص انتخاب می شود،به طوری که این دنباله،ملاکی را در بر می گیرد.به این معنی که هدف از دنبال کردن اشیا و تکرار های ان رسیدن به یک هدف می باشد.

در اینجا هدف استفاده از روش عقبگرد،رسیدن به جواب مساله وزیرها

می باشد.به طوری که هیچ دو وزیری در یک صفحه شطرنج همدیگر را گارد ندهند.

توضیح و تشریح مساله:

1)تعریف مساله:

تعیین جوابهای مساله،یعنی جاهایی که چند وزیر می توانند در یک صفحه شطرنج

 قرار بگیرند ،به صورتی که هیچ کدام همدیگر را گارد ندهند یا به عبارتی همدیگر را تهدید نکنند.(یا به عبارتی هیچ دو وزیری در یک سطر یا ستون قرار نگیرند.)

که تعداد وزیر ها و صفحه شطرنج می باشد.N2)ورودی های مساله:

3)خروجی :مکانهای امنی که وزیر ها می توانند در انها قرار بگیرند.

خروجی برنامه در نهایت به صورت زیر می باشد:

ارایه ای از اعدا صحیح که از یک تا عددی که در ورودی مشخص می شود،موقعیت وزیر ها را در صفحات شطرنج مشخص می کند.

الگوریتم کلی برنامه:

تابع بکار رفته د الگوریتم و کاربرد آنها:

Promising():

کار بررسی امید بخش بودن یا نبودن را انجام می دهد.وقتی مقدار صفر را برمی گرداند که یک گره و اجداد آن ،وزیرها را در یک سطر یا ستون قرار دهند.هر گره توسط یک زوج مرتب نگه داشته می شود.

تابع دوم:

Queens():

فراخوانی تابع امید بخش و گرفتن نتیجه از ان تابع و در صورت امید بخش بودن محاسبه جواب و بازگرداندن آن به خروجی برنامه.

Void queens (index i)

{

 Index  j;

If ( promising(i) )

  if ( i == n )

        cout<

  else

       for ( j=1 ;j<=n ;j++)

       col[i+1]=j;   //see if queen in (i+1) st row

       queens(i+1);

       }

}

bool promising (index i)

{

 index k;

 bool change ;

 k=1;

 change:=true;

 while (k

 {