اشکال کد مسئله وزیرها

[sa1378]

سلام
من برای مسئله وزیر ها کد زیر رو زدم ولی مثلا برای وردی 8 میگه چیزی پیدا نشده...ولی برای 5 درسته
#include <iostream>
#include <stdlib.h>
using namespace std;
#define N 1000
int n,ans[N];
bool col[N],dia1[N],dia2[N];


bool calc(int i)
{
if(i==n)
return true;
for(int j=0;j<n;j++)
{
if(col[j]==false && dia1[abs(i-j)]==false && dia2[i+j]==false)
{
col[j]=dia1[abs(i-j)]=dia2[i+j]=true;
ans[i]=j;
if(calc(i+1)==true)
return true;
col[j]=dia1[abs(i-j)]=dia2[i+j]=false;
}
}
return false;
}

int main() {
cin>>n;
if(calc(0)==true)
for(int i=0;i<n;i++)
cout<<i+1<<" "<<ans[i]+1<<endl;
else
cout<<"Not Valid";
return 0;
}

[shahmohammadi]

سلام.
این طور که من دیدم فقط برای 1 تایی و 5 تایی جواب می ده.
متوجه الگوریتمتون نشدم. حتما الگوریتمتون مشکل داره.
دقیق ترین و پر هزینه ترین روش back tracking هست، که همه‎ی راه های ممکن رو امتحان می کنه تا به یک جواب درست برسه. روش های خطادار ولی کم هزینه تر هم روش هایی مثل الگوریتم ژنتیک هست که ممکنه جوابی با خطا به دست بیاره.

اگر از حالت اول استفاده کنید، یه کد بنویسید که تمام جایگشت های ممکن بین اعداد 1 تا n رو بدست بیاره. در هر مرحله که یکی از جایگشت ها به دست اومد، بررسی کنه ببینه که آیا این آرایه جواب درستی هست یا نه.
مثلا اگر در مرحله ای جایگشت 3 5 2 4 1 رو داد بررسی کنه ببینه که اگر وزیر ها رو این جوری بچینید تعداد 0 خطا خواهید داشت. و در نتیجه به جواب خواهید رسید.
چون این الگوریتم رشد نمایی داره برای n های بزرگ نمی شه به کار برد.

[sa1378]

این BACK TRACKING هست دیگه..
از راس صفر شروع میکنه تا N
COL برای اینه که ببینیم در این ستون وزیر دیگه ای قبلا بوده یا نه
DIA1,DIA2 هم برای بررسی قطر هاست

[shahmohammadi]

درسته، من زیاد به کد توجه نکردم.
به نظرم اینجا یه چیزی می خواهد:

if(calc(i+1)==true)
return true;
else { /* here */}

یعنی وقتی دیدیم که با انتخاب j برای این i به نتیجه نمی رسیم باید یه چیز دیگه انجام بدیم.
ایراد کارش همین جاست.

[sa1378]

گفتم که اگه نشد
col[j]=dia1[abs(i-j)]=dia2[i+j]=false;
بعد هم false برگردون

[shahmohammadi]

اینم درسته.

اشکال کارت اینجاست که dia1 درست نیست.

کد زیر رو به ازای ورودی 4 اجرا کن و به خروجی توجه کن:

#include <iostream>
#include <stdlib.h>
using namespace std;
#define N 1000
int n,ans[N];
bool col[N],dia1[N],dia2[N],dia3[N];
int I;
bool calc(int i)
{
if(i==n)
return true;

for(int k=0;k<I;k++)cout<<" ";
cout<<i<<"{ "<<endl;
I++;
for(int j=0;j<n;j++)
{
for(int k=0;k<I;k++)cout<<" ";
cout<<"j = "<<j<<endl;
for(int k=0;k<I;k++)cout<<" ";
for(int k=0;k<=n;k++)
cout<<dia1[k]<<" ";
cout<<"\n";
for(int k=0;k<I;k++)cout<<" ";
for(int k=0;k<=n+n;k++)
cout<<dia2[k]<<" ";
cout<<"\n";
for(int k=0;k<I;k++)cout<<" ";
for(int k=0;k<=n;k++)
cout<<col[k]<<" ";
cout<<"\n";
if(i==2&& j==0){
if(col[j]==false) cout<< "col[j]==false\n";
if(dia1[abs(i-j)]==false) cout<< "dia1[abs(i-j)]==false\n";
if(dia2[i+j]==false) cout<< "dia2[i+j]==false\n";
}
if(col[j]==false && dia1[abs(i-j)]==false && dia2[i+j]==false)
{
col[j]=dia1[abs(i-j)]=dia2[i+j]=true;
for(int k=0;k<I;k++)cout<<" ";
cout<<"ans[ "<<i<<" ] = "<<j<<endl;
ans[i]=j;
for(int k=0;k<I;k++)cout<<" ";
cout<<"array is: ";
for(int k=0;k<=i;k++)
cout<<ans[k]<<" ";
cout<<"\n";

if(calc(i+1)==true)
return true;
col[j]=dia1[abs(i-j)]=dia2[i+j]=false;
}
}
I--;
for(int k=0;k<I;k++)cout<<" ";
cout<<i<<"} "<<endl;

return false;
}

int main() {
cin>>n;
if(calc(0)==true)
for(int i=0;i<n;i++)
cout<<i+1<<" "<<ans[i]+1<<endl;
else
cout<<"Not Valid";

cin>>n;
return 0;

}



همونطور که می بینی زمانی که برای ans0 عدد 1 انتخاب شده و بعد برای ans2 عدد 3 انتخاب شده، باید عدد 0 برای ans3 انتخاب شه ولی چون dia1 غلطه فکر می کنه که نمی شه اون خونه رو اجرا کرد.
توی شکل زیر هنگامی که در i=1 و j=3 خونه شماره 3 انتخاب شده، dia1[3-1] یعنی dia1[2] ترو شده. در ادامه کد، زمانی که i=2 هست و j=0 باید خونه 0 انتخاب شه. ولی چون dia1[2-0] میشه همون خونه ای که قبلا ترو شده، نمی تونه انتخاب شه. بنا براین باید dia1 رو اصلاح کنی. در واقع دیا1 می گه که خونه های 3 و 0 هم رو می زنند.


126051