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

[amir_narmafzar]

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

[MM_Mofidi]

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

[Sepidar]

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

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

const
ChessDim=8;
TotalProgress=ChessDim*ChessDim*ChessDim*ChessDim* ChessDim*ChessDim*ChessDim*ChessDim;
type
TQChessBoard=array [1..ChessDim] of byte;

function Acceptable(ABoard:TQChessBoard):Boolean;
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]) 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.

[aftab]

سلام!
این هم همون کار رو میکنه! :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++;
}

[seyedof]

سلام
این یک مسئله جالب و قدیمیه. الگوریتم جناب کامبیز خان رو نخوندم ولی فکر کنم از روش 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.
}
}
}
}
}
}
}
}