طراحی الگوریتمی که هشت وزیر را در صفحه شطرنج طوری قرار دهد

طراحی الگوریتمی که هشت وزیر را در صفحه شطرنج طوری قرار دهد که یکدیگر را تهدید نکنند؟

باید دونه دونه بگذاری در اولین موقعیت بدون خطر تا بجایی برسی که نشود نوشت بعد برگردی یکی را جابجا کنی... الی آخر.
بعضی نکات شما را جلو میاندازد مثل اینکه هیچ دوتایی در یک سطر یا ستون نمیتوانند قرار گیرند
:موفق:

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

خوب این هم از کد من:

const

 ChessDim=8;

 TotalProgress=ChessDim*ChessDim*ChessDim*ChessDim*  ChessDim*ChessDim*ChessDim*ChessDim;

type

 TQChessBoard=array [1..ChessDim] of byte;



function Acceptable(ABoard:TQChessBoard):Bo  olean;

var

 ok:boolean;

 i,j:byte;

begin

 ok:=true;

 i:=0;

 repeat

     inc(i);



     j:=i+1;

     while ok and (j<=ChessDim) do begin

        ok:=ok and

            (ABoard[i]<>ABoard[j]&#4  1; and

            (abs(ABoard[i]-ABoard[j])<>(j-i));



        inc(j);

     end;



 until not ok or (i>ChessDim);



 Acceptable:=ok;

end;



procedure WriteBoard(ABoard:TQChessBoard);

var

 i:Byte;

begin

 writeln;

 for i:=1 to ChessDim do write(ABoard[i]:3);

 writeln;

end;



var

 Board:TQChessBoard;

 Progress:longint;



procedure ProcessConditions(Depth:byte);

var

 i:byte;

begin

 if Depth>ChessDim then

    begin

      inc(Progress);

      write(Progress{/TotalProgress:5:2,' %  '},#13);

      if Acceptable(Board) then WriteBoard(Board);

    end

 else

    for i:=1 to ChessDim do begin

       Board[Depth]:=i;

       ProcessConditions(Depth+1);

    end;

end;



begin

 writeln;

 writeln('Total: ',TotalProgress);

 Progress:=0;

 ProcessConditions(1);

end.

سلام!
این هم همون کار رو میکنه! :wise1: :wise1:

#include <stdio.h> 

#include <conio.h> 

#include <math.h> 



int col1[8]; 



void q(int); 

int p(int,int *); 







main() 

{ 

int a=0; 

clrscr(); 

//for(a=0;a<8;a++) 

//col1[a]=0; 

q(0); 

} 



void q(int i) 

{ 

int j=0,b,c; 

//if(p(i,col1)==1) 

b=p(i,col1); 

if(b==1) 

if(i==8) 

{ 

for(c=1;c<=8;C++‎) 

printf("%d\t",col1[c]); 

getch(); 

printf("\n"); 

} 

else 

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

{ 

col1[i+1]=j; 

q(i+1); 

} 

} 



int p(i,col2) 

int i,col2[]; 

{ 

int k=1,s; 

s=1; 

while(k<i && s==1) 

{ 

if(col2[i]==col2[k] || abs(col2[i]-col2[k])==i-k) 

s=0; 

k++; 

}

سلام
این یک مسئله جالب و قدیمیه. الگوریتم جناب کامبیز خان رو نخوندم ولی فکر کنم از روش Brute Force است یعنی همه حالات ممکن رو تست میکنه.
هشت وزیر رو به
64!/(64-8)!

حالت میشه توی صفحه شطرنج قرارداد (عدد بزرگیه) که میشه همه این حالات رو تولید کرد و بعد هر حالت رو تست کرد که ببینیم توی مجموعه جواب هست یا نه. اما در اینجور مسایل یک راه برای تسریع برنامه کوچک کردن فضای مسئله یا فضای حالات است به این ترتیب که تا جای امکان خیلی از حالات رو بدون چک کردن حذف کنیم.

مثلا سطر به سطر بریم پایین تا از قراردادن دو وزیر در یک سطر جلوگیری بشه اینطوری تعداد حالات تولید شده خیلی کمتر میشه و میشه ۸ به توان ۸ .
اما این هم تقریبا عدد بزرگیه و میشه در هر سطر که وزیر میگذاریم از برخورد در ستونها هم اجتناب کنیم به این ترتیب که در سطر اول ۸ انتخاب داریم در سطر بعدی ۷ تا در سطر بعدی ۶ تا و الی آخر. اینطوری فضای حالات میشه ۸ فاکتوریل و الگوریتمش هم میشه چیزی توی مایه های تولید جایگشتهای۸ شی.

در این حالت تعداد کل حالتهای چک شده ۸! است که میشه حدود ۴۲۰۰۰ حالت و فقط کافیه که تهدید قطری رو چک کنیم چون با این روش تولید حالات، حالتهای تهدید افقی یا عمودی اصلا داخل مجموعه تست نمیان.

ممنون علی

من مدتیه از کار کردن روی این الگوریتمها دورم و شاید نظرم درست نباشد. اما چیزی که یادم میاد اینه که باید همه موارد رو امتحان کرد. و زمان خیلی زیادی نمی برد. در واقع در کسری از ثانیه جواب رو می داد.
با نظر مدیر بخش آقای Seyedof موافقم که می شه بعضی حالات رو حذف کرد. ولی نمی دونم چطور می شه تهدید ستونی رو از قبل حذف کرد. در واقع فکر می کنم راه درست اینه که هشت وزیر رو در هشت سطر در نظر گرفت و ستونهاشون رو جابجا کرد. در پیام بعدی منظورم رو کد می کنم

اینم کد !

int Diff( int i , int j )

{

   return ( abs(i-j) ) ;

// I'm not sure about function abs. I mean a function return abstract of a number abs(-1) = abs(1) = 1

}



void main(void)

{

// Declaration of I1.. I8

for ( I1 = 0 ; I1 < 8 ; I1++)

 for ( I2 = 0 ; I2 < 8 ; I2++)

  {

     if (Diff(I2 , I1) == 0) continue;

     if (Diff(I2 , I1) == 1) continue;

     for ( I3 = 0 ; I3 < 8 ; I3++)

     {

       if (Diff(I3 , I1) == 0) continue;

       if (Diff(I3 , I1) == 2) continue;

       if (Diff(I3 , I2) == 0) continue;

       if (Diff(I3 , I2) == 1) continue;

       for ( I4 = 0 ; I4 < 8 ; I4++)

       {

         if (Diff(I4 , I1) == 0) continue;

         if (Diff(I4 , I1) == 3) continue;

         if (Diff(I4 , I2) == 0) continue;

         if (Diff(I4 , I2) == 2) continue;

         if (Diff(I4 , I3) == 0) continue;

         if (Diff(I4 , I3) == 1) continue;

         for ( I5 = 0 ; I5 < 8 ; I5++)

         {

            if (Diff(I5 , I1) == 0) continue;

            if (Diff(I5 , I1) == 4) continue;

            if (Diff(I5 , I2) == 0) continue;

            if (Diff(I5 , I2) == 3) continue;

            if (Diff(I5 , I3) == 0) continue;

            if (Diff(I5 , I3) == 2) continue;

            if (Diff(I5 , I4) == 0) continue;

            if (Diff(I5 , I4) == 1) continue;

            for ( I6 = 0 ; I6 < 8 ; I6++)

            {

               if (Diff(I6 , I1) == 0) continue;

               if (Diff(I6 , I1) == 5) continue;

               if (Diff(I6 , I2) == 0) continue;

               if (Diff(I6 , I2) == 4) continue;

               if (Diff(I6 , I3) == 0) continue;

               if (Diff(I6 , I3) == 3) continue;

               if (Diff(I6 , I4) == 0) continue;

               if (Diff(I6 , I4) == 2) continue;

               if (Diff(I6 , I5) == 0) continue;

               if (Diff(I6 , I5) == 1) continue;

               for ( I7 = 0 ; I7 < 8 ; I7++)

               {

                 if (Diff(I7 , I1) == 0) continue;

                 if (Diff(I7 , I1) == 6) continue;

                 if (Diff(I7 , I2) == 0) continue;

                 if (Diff(I7 , I2) == 5) continue;

                 if (Diff(I7 , I3) == 0) continue;

                 if (Diff(I7 , I3) == 4) continue;

                 if (Diff(I7 , I4) == 0) continue;

                 if (Diff(I7 , I4) == 3) continue;

                 if (Diff(I7 , I5) == 0) continue;

                 if (Diff(I7 , I5) == 2) continue;

                 if (Diff(I7 , I6) == 0) continue;

                 if (Diff(I7 , I6) == 1) continue;

	         for ( I8 = 0 ; I8 < 8 ; I8++)

                 {

                     if (Diff(I8 , I1) == 0) continue;

                     if (Diff(I8 , I1) == 7) continue;

                     if (Diff(I8 , I2) == 0) continue;

                     if (Diff(I8 , I2) == 6) continue;

                     if (Diff(I8 , I3) == 0) continue;

                     if (Diff(I8 , I3) == 5) continue;

                     if (Diff(I8 , I4) == 0) continue;

                     if (Diff(I8 , I4) == 4) continue;

                     if (Diff(I8 , I5) == 0) continue;

                     if (Diff(I8 , I5) == 3) continue;

                     if (Diff(I8 , I6) == 0) continue;

                     if (Diff(I8 , I6) == 2) continue;

                     if (Diff(I8 , I7) == 0) continue;

                     if (Diff(I8 , I7) == 1) continue;

                     // This is a souloution. Show it please . I think the number of solution is more than 100.

                 }

              }

           }

         }

       }

     }

  }

}