- تاریخ عضویت
- 22 ژانویه 2006
- نوشته‌ها
- 60
- لایک‌ها
- 0
به نقل از Arash_j13 :
این روش رو یه جور واضحتر قبلا شنیده بودم که باید به خونه ای رفت که از اون خونه به کمترین خونه های ممکن بشه رفت.
حل مسئله:
(اصل برنامه 20 خطه بقیش کارای گرافیکیه و ... است).
کد:
#include<stdio.h>
#include<conio.h>
#define Cbakg 1
#define Cbakgtxt 2
#define Cbakgshattxt 4
#define Cbakgshatsiah 0
#define Cbakgshatsefid 7
void shat3(int x,int y,int nx,int ny,int tnx,int tny,int cse,int csi)
{
int i,j,k,l,m=0;
gotoxy(x,y);
for(i=0;i<tny;i++)
for(j=0;j<ny;j++){
m++;
for(k=0;k<tnx;k++){
if((i+k)%2==0)
textbackground(cse);
else
textbackground(csi);
for(l=0;l<nx;l++)
cprintf(" ");
}
gotoxy(x,y+m);
}
}
void main()
{
int sh[12][12]={0};
int h[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},
{-1,-2},{1,-2},{2,-1}};
int k=0,x,y,step=1,xNew,yNew,num,minNum=9,minK;
int l,i,j;
char ch;
textbackground(Cbakg);
textcolor(Cbakgtxt);
clrscr();
/////////////
//initialize
for(i=0;i<12;i++){
sh[i][0]=sh[i][1]=sh[i][10]=sh[i][11]=-1;
sh[0][i]=sh[1][i]=sh[10][i]=sh[11][i]=-1;
}
cprintf("inter x,y ");
scanf("%d%d",&x,&y);
x=(x-1)%8+1;
y=(y-1)%8+1;
clrscr();
cprintf("inter x,y x=%d y=%d",x,y);
x++;
y++;
sh[x][y]=step;
/////////////////
//begin calculate
for(step=2;step<=64;step++){
minNum=9;
for(k=0;k<8;k++){
xNew= x + h[k][0];
yNew= y + h[k][1];
if( sh[xNew][yNew] == 0){
sh[xNew][yNew] = step;
num=0;
for(l=0;l<8;l++)
if(sh[ xNew + h[l][0] ][ yNew + h[l][1] ]==0) num++;
if(num<minNum){
minNum=num;
minK=k;
}
sh[xNew][yNew] = 0;
}
}
x= x + h[minK][0];
y= y + h[minK][1];
sh[x][y]=step;
}
//end calculate
///////////////
///////////////
//output
textcolor(Cbakgshattxt);
shat3(10,1,8,3,8,8,Cbakgshatsiah,Cbakgshatsefid);
for(i=0;i<8;i++)
for(j=0;j<8;j++){
if((i+j)%2==0)
textbackground(Cbakgshatsiah);
else
textbackground(Cbakgshatsefid);
gotoxy(j*8+13,i*3+2);
cprintf("%2d",sh[i+2][j+2]);
}
textcolor(Cbakgtxt);
textbackground(Cbakg);
gotoxy(20,25);
cprintf("if you want run step by step press y ");
ch=getch();
if(ch=='y'||ch=='Y'){
clrscr();
shat3(10,1,8,3,8,8,Cbakgshatsiah,Cbakgshatsefid);
textcolor(Cbakgshattxt);
for(i=1;i<65;i++){
for(j=0;j<8;j++)
for(l=0;l<8;l++)
if(sh[j+2][l+2]==i){
if((l+j)%2==0)
textbackground(Cbakgshatsiah);
else
textbackground(Cbakgshatsefid);
gotoxy(l*8+13,j*3+2);
cprintf("%2d",i);
gotoxy(80,25);
}
ch=getch();
if(ch=='q'||ch=='Q')break;
}
}
}آرایه sh درسته که 12*12 هست ولی در واقع خود صفحه شطرنج هستش که به این صورت مقدار دهی اولیه کردم:
کد:
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1آرایه h هم که نحوه حرکت اسب رو شبیه سازی می کنه. هر کدوم از هشت جفت عددهای آرایه h یک حرکت اسب هست. و چون اسب از هر خونه حداکثر به هشت خانه بعدی می تونه بره پس آرایه h هشت جفت عدد داره.
این روش فقط چند حالت از میلیونها جواب رو میده. این سئوال رو قبلا در حالت کلیش رو مجبور بودم حل کنم یعنی تمام حالتهایی که اسب می تونه همه خونه ها رو در 64 حرکت بره .
اینطوری خیلی سخت تر میشه این هم بعنوان یک سئوال بهش فکر کنید . من قبلا حل کردم (کلا تغییرش دادم تا جواب این سئوال رو بدم) البته برنامه با این روش راه حل های زیادی رو پیدا می کنه ولی نمی تونه همه راه حل ها رو پیدا کنه باید 64^8 حالت رو چک کنه که در حدود همون برنامه قبلی در میاد (یعنی یکسال). توی سه یا چهار ساعت 3000 تا جواب رو بدست میاره (بستگی به نقطه شروع داره) برای همین کل جواب ها باید بیشتر از چند میلیون باشه.
حالا همین خودش دوباره سئوال باشه. یعنی برنامه ای که بتونه تمام راه حل ها رو بدست بیاره.
روش جالبی داره ولی سخت تره.
