رفتن به مطلب
اطلاعیه مهم: پایان فعالیت انجمن پس از 15 سال ×
اطلاعیه مهم: پایان فعالیت انجمن پس از 15 سال

مسئله هشت وزير Queens

spow

توسط spow،
در برنامه نویسی

ارسال های توصیه شده

spow    44197

spow
ارسال شده در

مسئله هشت وزير

 

صورت مسئله : هشت وزير را در هشت خانه شطرنج (8*8) طوري قرار دهيد كه هيچكدام يكديگر را تهديد نكنند. وزير در خانه هاي شطرنج به صورت عرضي،طولي و قطري مي تواند حركت كند. اين مسئله قابل تعميم به مسئله N وزير در يك شطرنج N*N است.

 

تاريخچه: اين مسئله در سالي 1848 توسط شطرنج بازي به نام Max Bezzel عنوان شد و رياضي دانان بسياري ازجمله Gauss و Georg Cantor بر روي اين مسئله كار كرده و در نهايت آنرا به N وزير تعميم دادند. اولين راه حل توسط Franz Nauck در سال 1850 ارائه شد كه به همان مسئله N وزير تعميم داده شد. پس از آن Gunther راه حلي با استفاده از دترمينان ارائه داد كه J.W.L. Glaisher آنرا كامل نمود.

در سال 1979 ، Edsger Dijkstra با استفاده از الگوريتم عقب گرد اول عمق اين مسئله را حل كرد.

 

راه حل: براي حل اين مسئله كه داراي 92 جواب است ، بايد تكنيكهايي جهت كاهش حالات ،روش Brute Force يا امتحان تك تك جواب ها انجام شود. تعداد همه حالاتي كه مي تواند در روش Brute Force چك شود برابر 16,777,216 يا هشت به توان هشت است!

يكي از روش هاي حل اين مسئله براي n>=4 يا n=1 استفاده از روش مكاشفه اي (heuristic) است:

1- عدد n را بر عدد 12 تقسيم كن و باقي مانده را يادداشت كن

2- به ترتيب اعداد زوج 2 تا n را در ليستي بنويس

3- اگر باقي مانده 3 يا 9 بود ، عدد 2 را به انتهاي ليست انتقال بده.

4- به ليست اعداد فرد 1 تا N را به ترتيب اضافه كن، اما اگر باقي مانده 8 بود اعداد را دو به دو باهم عوض كند (مثلا 1و3و5و7و9 تبديل به 3و1و7و5و9 ميشه)

5- اگر باقي مانده 2 بود جاي 1 و3 را با هم عوض كن و 5 را به انتهاي ليست ببر

6- اگر باقي مانده 3 يا 9 بود ، اعداد 1 و 3 را به انتهاي ليست ببر.

7- حال با استفاده از ليست بدست آمده وزير ها در صفحه شطرنج چيده مي شوند، بطوريكه جاي وزير ستون اول ،اولين عدد ليست ،جاي وزير ستون دوم ، دومين عدد ليست و ...

اين الگوريتم يك راه حل براي حل اين مسئله است، براي بدست آوردن همه حالات از روشهاي ديگري مي توان استفاده كرد.

روش حل مسئله 12 راه حل يكتا دارد كه با در نظر گيري تقارن و چرخش به 92 حالت قابل تبديل است.

  • Like 4
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

برنامه 8 وزیر در c

 

 

 

#include

#include

#include

#include

#include

 

#define TRUE 1

#define FALSE 0

 

unsigned int a,b,c,d,e,f,g,h;

void main(void)

{

unsigned char chk_crash(unsigned char,unsigned char,unsigned char);

void draw_puzzle(void);

clrscr();

for (a=1;a

for (b=1;b

if (chk_crash(a,b,1))

for (c=1;c

if ((chk_crash(c,b,1)) && (chk_crash(c,a,2)))

for (d=1;d

if ((chk_crash(d,c,1)) && (chk_crash(d,b,2)) && (chk_crash(d,a,3)))

for(e=1;e

if ((chk_crash(e,d,1)) && (chk_crash(e,c,2)) && (chk_crash(e,b,3)) && (chk_crash(e,a,4)))

for (f=1;f

if ((chk_crash(f,e,1)) && (chk_crash(f,d,2)) && (chk_crash(f,c,3)) && (chk_crash(f,b,4)) && (chk_crash(f,a,5)))

for (g=1;g

if ((chk_crash(g,f,1)) && (chk_crash(g,e,2)) && (chk_crash(g,d,3)) && (chk_crash(g,c,4)) && (chk_crash(g,b,5)) && (chk_crash(g,a,6)))

for (h=1;h

if ((chk_crash(h,g,1)) && (chk_crash(h,f,2)) && (chk_crash(h,e,3)) && (chk_crash(h,d,4)) && (chk_crash(h,c,5)) && (chk_crash(h,b,6)) && (chk_crash(h,a,7)))

{

draw_puzzle();

getch();

}

getch();

}

unsigned char chk_crash(unsigned char i,unsigned char j,unsigned char d)

{

if ((i==j) || (abs(i-j)==d))

return(FALSE);

else

return(TRUE);

}

void draw_puzzle(void)

{

unsigned char a1,b1,a2,b2,i,v;

clrscr();

for (a1=1;a1

for (b1=18;b

{

gotoxy(b1,a1+d);

a2=(a1-1)/2+1;

b2=(b1-18)/6+1;

if (((a2+b2)%2)==0)

textcolor(11);

else

textcolor(1);

cprintf("A\0");

for (i=0;i

{

switch(i)

{

case 0:{v=a;break;}

case 1:{v=b;break;}

case 2:{v=c;break;}

case 3:{v=d;break;}

case 4:{v=e;break;}

case 5:{v=f;break;}

case 6:{v=g;break;}

case 7:{v=h;break;}

}

gotoxy(15+6*v,5+i*2);

cprintf("*\0");

}

}

}

  • Like 3
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

ایناهم برنامه ها وسورس هایی هستند که دوستان برنامه نویس برای مسئله هشت وزیر یا برنامه جستجوی تپیه نوردی تحت c نوشتند

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

  • Like 2
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

هشت وزیر

نویسنده : علی مشاطان

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

هشت وزیر یکی از بازهای شطرنج است که 8 وزیر را باید جوری در خانه های شطرنج قرار دهید که وزیر ها همدیگر را نزنند (میدانید که وزیر در شطرنج ترکیب حرکت فیل و رخ است ) و اینجا قصد دارم به کمک کامپیوتر برنامه بنویسیم که هر 92 حالت آن را نمایش دهد. الگوریتم برای به دست آوردن مهره ها به وسیله Back Tracking نوشته شده.

برای Compile برنامه در Delphi باید Component : ChessBoard نصب کنید.

  • Like 2
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

برنامه کامل 8 وزیر به همراه سورس

 

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

  • Like 3
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

برنامه نحوه چيدن 8 وزير در صفحه شطرنج به زبان c++

#include

#include

#include

#include

#include

#include

#define EMPTY 48

#define ESCAPE 27

void show(int *minister, int answer);

void main()

{

int minister[8] = {0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08};

register int i = 0, j = 0, k = 0, l = 0, m = 0, n = 0, o = 0, p = 0;

register int s, s1, answer = 0;

char flag[8][8];

char ch;

int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, "");

errorcode = graphresult();

if (errorcode != grOk)

{

cprintf("Graphics error: %s\n", grapherrormsg(errorcode));

cprintf("Press any key to halt:");

getch();

exit(1);

}

while(i

minister[0] = 8;

j = 0;

k = 0;

l = 0;

m = 0;

n = 0;

o = 0;

p = 0;

memset(flag, EMPTY, 64);

minister[0] = i;

for(s = i; s >= 0; s--)

flag[i - s] = 'i';

for(s = i; s

flag[s - i] = 'i';

for(s = 1; s

flag = 'i';

while(j

minister[1] = 8;

for(s = 0; s

for(s1 = 1; s1

if(flag[s1] > 'i'){

flag[s1] = EMPTY;

k = 0;

l = 0;

m = 0;

n = 0;

o = 0;

p = 0;

}

while(flag[j][1] != EMPTY)

j++;

if(j

minister[1] = j;

for(s = j; s >= 0; s--)

if( (j - s + 1)

flag[j - s + 1] = 'j';

for(s = j; s

if( (s - j + 1)

flag[s - j + 1] = 'j';

for(s = 2; s

if(flag[j] == EMPTY)

flag[j] = 'j';

}

if(j

while(k

minister[2] = 8;

for(s = 0; s

for(s1 = 2; s1

if(flag[s1] > 'j'){

flag[s1] = EMPTY;

l = 0;

m = 0;

n = 0;

o = 0;

p = 0;

}

while(flag[k][2] != EMPTY && k

k++;

if(k

minister[2] = k;

for(s = k; s >= 0; s--)

if( (k - s + 2)

flag[k - s + 2] = 'k';

for(s = k; s

if( (s - k + 2)

flag[s - k + 2] = 'k';

for(s = 3; s

if(flag[k] == EMPTY)

flag[k] = 'k';

}

if(k

while(l

minister[3] = 8;

for(s = 0; s

for(s1 = 3; s1

if(flag[s1] > 'k'){

flag[s1] = EMPTY;

m = 0;

n = 0;

o = 0;

p = 0;

}

while(flag[l][3] != EMPTY && l

l++;

if(l

minister[3] = l;

for(s = l; s >= 0; s--)

if( (l - s + 3)

flag[l - s + 3] = 'l';

for(s = l; s

if( (s - l + 1)

flag[s - l + 3] = 'l';

for(s = 4; s

if(flag[l] == EMPTY)

flag[l] = 'l';

}

if(l

while(m

minister[4] = 8;

for(s = 0; s

for(s1 = 4; s1

if(flag[s1] > 'l'){

flag[s1] = EMPTY;

n = 0;

o = 0;

p = 0;

}

while(flag[m][4] != EMPTY && m

m++;

if(m

minister[4] = m;

for(s = m; s >= 0; s--)

if( (m - s + 4)

flag[m - s + 4] = 'm';

for(s = m; s

if( (s - m + 4)

flag[s - m + 4] = 'm';

for(s = 5; s

if(flag[m] == EMPTY)

flag[m] = 'm';

}

if(m

while(n

minister[5] = 8;

for(s = 0; s

for(s1 = 5; s1

if(flag[s1] > 'm'){

flag[s1] = EMPTY;

o = 0;

p = 0;

}

while(flag[n][5] != EMPTY && n

n++;

if(n

minister[5] = n;

for(s = n; s >= 0; s--)

if( (n - s + 5)

flag[n - s + 5] = 'n';

for(s = n; s

if( (s - n + 5)

flag[s - n + 5] = 'n';

for(s = 6; s

if(flag[n] == EMPTY)

flag[n] = 'n';

}

if(n

while(o

minister[6] = 8;

for(s = 0; s

for(s1 = 6; s1

if(flag[s1] > 'n'){

flag[s1] = EMPTY;

p = 0;

}

while(flag[o][6] != EMPTY && o

o++;

if(o

minister[6] = o;

for(s = o; s >= 0; s--)

if( (o - s + 6)

flag[o - s + 6] = 'o';

for(s = o; s

if( (s - o + 6)

flag[s - o + 6] = 'o';

for(s = 7; s

if(flag[o] == EMPTY)

flag[o] = 'o';

o++;

}

if(o

while(p

minister[7] = 8;

while(flag[p][7] != EMPTY && p

p++;

if(p

minister[7] = p;

s1 = 0;

for(s = 0; s

if(minister

s1++;

if(s1 == 8){

show(minister, answer);

ch = getch();

if(ch == ESCAPE){

closegraph();

exit(1);

}

answer++;

}

}

p++;

}

o++;

}

n++;

}

m++;

}

l++;

}

k++;

}

j++;

}

i++;

}

closegraph();

}

void show(int *minister, int answer)

{

register int i;

char s[25], ch;

cleardevice();

sprintf(s, "%02d form(s) of answer.", answer + 1);

outtextxy(160, 10, s);

for(i = 0; i

line(i * 16, 0, i * 16, 128);

for(i = 0; i

line(0, i * 16, 128, i * 16);

for(i = 0; i

bar((i * 8) + 4, minister[i / 2] * 16 + 4, (i * 8) + 12, minister[i / 2] * 16 + 12);

outtextxy(10, 440, "Press any key to show another forms.(Espace for skip / Escape for end.)");

}

  • Like 3
لینک به دیدگاه

spow    44197

spow
  • مالک
ارسال شده در

بالاخره الگوریتم برنامه هشت وزیر رو پیدا کردم و نوشتمش. حتما همه با این برنامه آشنایی دارید.

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

 

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.
حجم : ۱۳۰ کیلوبایت

 

از وبلاگ اقای رضایی

  • Like 3
لینک به دیدگاه
رفتن به فهرست موضوع ها
×
×
  • اضافه کردن...