# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  معمای هشت یا 8Puzzle

## faezeh21

سلام 
کسی راه حلی برای حل معمای هشت (پازل هشت)داره .

----------


## k.robot

از *A با هیوریستیک مانهاتانی استفاده کن .تو کتاب هوش مصنوعی راسل فصل 4 توضیح داده شده.

----------


## whitehat

ظاهرا لینک ها Expire شده من دو PDF برای حل این مسئله در اینجا قرار می دهم.
توجه کنید که این مسئله به روش A* حل شده. در ضمن برای PDF دوم شما باید در مورد فاصله مانهاتان اطلاعات داشته باشید

----------


## Amateur_G

سلام.
اگه يكم بهم ريخته يا كمي درهمه ببخشيد.فرست نشد مرتبش كنم.
من براي محاسبه هزينه مسير دو مورد در نظر گرفتم:
1-تعداد خانه هايي كه در سر جاي خود قرار دارند
2-اينكه در صورت در نظر نگرفتن محدوديت ها چند حركت لازم است تا به جواب برسيم. 


//---------------------------------------------------------------------------#include<conio.h>
#include<math.h>
#include<stdio.h>
#pragmahdrstop
char pre_move;
int a[3][3];
int goal[3][3];
int zero_i,zero_j;
int stack[1000000];
int pop=0;
void find_zero();
void puzzle();
void exchange(int,int,int,int);
int h1();
int h2();
void output();
void input();
void save_Q(char);
void insert_goal();
#pragma argsused
//---------------------------------------------------------------------------int main()
{
input();
insert_goal();
puzzle();
getch();
return 0;
}
//**************************void insert_goal()
{
int i,j,s=1;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(i==2&&j==2)
s=0;
goal[i][j]=s;
s++;
}
}
//**************************void find_zero()
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(a[i][j]==0)
{
zero_i=i;
zero_j=j;
}
}
//**************************void exchange(int i,int j,int x,int y)
{
int temp;
temp=a[i][j];
a[i][j]=a[x][y];
a[x][y]=temp;
}
//**************************void input()
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
printf("enter number in [%d][%d]:\n",i,j);
scanf("%d",&a[i][j]);
if(a[i][j]<0||a[i][j]>8)
{
printf("WRONG DIGIT!!!");getch();
exit(0);
}
}
printf("/nplease wait...");
}
//******************************int h1()
{
int s=0,i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(a[i][j]==goal[i][j])
s++;
return s;
}
//******************************int h2()
{
int s,m,i,j,x,y;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(a[i][j]==goal[i][j])
s=0;
else
{
x=i,y=j;
while(a[i][j]!=goal[x][y])
{
x++;
if(x==3)
{
x=0;
y++;
}//end of if
if(y==3)
y=0;
}//end of while
s=(abs(x-i)+abs(y-j));
}//end of else
m+=s;
}//end of for(j)
return m;
}
//********************************void puzzle()
{
char next_move='h';int rh1,rh2,lh1,lh2,uh1,uh2,dh1,dh2,bh1,bh2;find_zero(  );
if(h1()==9)
output();
if(zero_j!=2&&pre_move!='l')
{
exchange(zero_i,zero_j,zero_i,zero_j+1);
rh1=h1();rh2=h2();next_move='r';
bh1=rh1;bh2=rh2;
exchange(zero_i,zero_j,zero_i,zero_j+1);
}
if(zero_j!=0&&pre_move!='r')
{
exchange(zero_i,zero_j,zero_i,zero_j-1);
lh1=h1();lh2=h2();
if(lh2<bh2||next_move=='h')
{
next_move='l';bh1=lh1;bh2=lh2;
}
exchange(zero_i,zero_j,zero_i,zero_j-1);
}
if(zero_i!=0&&pre_move!='d')
{
exchange(zero_i,zero_j,zero_i-1,zero_j);
uh1=h1();uh2=h2();
if(uh2<bh2||next_move=='h')
{
next_move='u';bh1=uh1;bh2=uh2;
}
exchange(zero_i,zero_j,zero_i-1,zero_j);
}
if(zero_i!=2&&pre_move!='u')
{
exchange(zero_i,zero_j,zero_i+1,zero_j);
dh1=h1();dh2=h2();
if(dh2<bh2||next_move=='h')
{
next_move='d';bh1=dh1;bh2=dh2;
}
exchange(zero_i,zero_j,zero_i+1,zero_j);
}
pre_move=next_move;
switch ((next_move)){
case'l':
exchange(zero_i,zero_j,zero_i,zero_j-1);
save_Q(next_move);
puzzle();
break;
case'r':
exchange(zero_i,zero_j,zero_i,zero_j+1);
save_Q(next_move);
puzzle();
break;
case'u':
exchange(zero_i,zero_j,zero_i-1,zero_j);
save_Q(next_move);
puzzle();
break;
case'd':
exchange(zero_i,zero_j,zero_i+1,zero_j);
save_Q(next_move);
puzzle();
break;
default:
printf("ERROR!!!");
exit(0);
}//end of switch
}//***********************************void output()
{
int i;
printf("\n");
for(i=0;i<=pop;i++)
printf("%c",stack[i]);
printf("\njob's done!!!");
getch();
exit(0);
}
//***********************************void save_Q(char c)
{
pop++;
if(pop==1000000)
{
printf("\nOVERFLOW!!!");
exit(0);
}
stack[pop]=c;
}
//***********************************اميدوارم مفيد باشه . :تشویق:

----------


## PHP000001

جناب Amateur_G از روش A* استفاده کردین؟

----------


## PHP000001

با تشکر از Amateur_G 
 این برنامه ای که نوشتید در واقع Best-First است. برای A* نمیدونید شرط  
 h>=h* چطور باید اعمال بشه؟
 h:هزینه تخمینی ارزانترین مسیر از گره n به گره هدف
 h*: ارزانترین مسیر واقعی از گره n به هدف
 یعنی اول باید هزینه واقعی رو در بیاریم و شرط رو بر اساس اون بزاریم؟؟؟؟

----------


## محمدامین شریفی

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

----------


## محمدامین شریفی

در این سایت با applet های جاوا و توضیح خوب و ساده،روش های جستجوی BFS , DFS  و IDS را به صورت انیمیشن و متن، شرح داده است.
دوستان نظری در تکمیل گفته های این سایت درباره حل معمای هشت[و معمای پانزده] دارند؟

----------


## mjtbasady

سلام .منم حل معمای هشت با روش آنالیز شبیه سازی شده رو میخوام.
کسی میتونه کمک کنه؟

----------


## qwerty11

> با تشکر از Amateur_G 
>  این برنامه ای که نوشتید در واقع Best-First است. برای A* نمیدونید شرط  
>  h>=h* چطور باید اعمال بشه؟
>  h:هزینه تخمینی ارزانترین مسیر از گره n به گره هدف
>  h*: ارزانترین مسیر واقعی از گره n به هدف
>  یعنی اول باید هزینه واقعی رو در بیاریم و شرط رو بر اساس اون بزاریم؟؟؟؟



سلام،
در مورد حل پازل پانزدهتایی من جایی ندیدم که درباره ی جواب بهینش چیزی گفته باشن، اما اگه تو صفحه ی ویکیپدیاش بری یه راه برای حل معما گفتن : تبدیل کردن پازل 15 به پازل 8. به این ترتیب که اول سطر اول و ستون اولش رو میچینی و بعدش مسئله به معمای هشت تبدیل میشه. البته جواب بهینه رو نمیده.

حل معمای هشت با جستجوی اول سطح هم کار آسونیه، فقط کافیه کاری کنی تا وقتی به یه گره تکراری رسیدی بتونی سریع تشخیص بدی و در واقع search رو با (1)O انجام بدی که اگه بتونی هر گره رو یه string در نظر بگیری میتونی اینکار رو با map توی C++‎‎‎ و HashTable توی جاوا انجام بدی.

جستجوی عمیق کننده ی تکراری هم همونطور که از اسمش پیداست باید فقط وقتی DFS میزنی، اگه به عمق محدود مورد نظر رسیدیم دیگه گره رو ادامه ندیم و  عمق محدود مورد نظر رو یکی افزایش بدیم تا وقتی که بتونیم تو یه عمقی به جواب برسیم. این روش هم مثل جستجوی اول سطح جواب بهینه رو به ما میده ... h که همون هزینه ی تخمینی هست برابر فاصله ی manhattan گره از goal هستش بعلاوه ی هزینه ای که تا اینجا اومدیم.

----------


## omidarbabi

#include<conio.h>
#include<math.h>
#include<stdio.h>
#pragmahdrstop
char pre_move;
int a[3][3];
int goal[3][3];
int zero_i,zero_j;
int stack[1000000];
int pop=0;
void find_zero();
void puzzle();
void exchange(int,int,int,int);
int h1();
int h2();
void output();
void input();
void save_Q(char);
void insert_goal();
#pragma argsused
//---------------------------------------------------------------------------int main()
{
input();
insert_goal();
puzzle();
getch();
return 0;
}
//**************************void insert_goal()
{
int i,j,s=1;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(i==2&&j==2)
s=0;
goal[i][j]=s;
s++;
}
}
//**************************void find_zero()
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(a[i][j]==0)
{
zero_i=i;
zero_j=j;
}
}
//**************************void exchange(int i,int j,int x,int y)
{
int temp;
temp=a[i][j];
a[i][j]=a[x][y];
a[x][y]=temp;
}
//**************************void input()
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
printf("enter number in [%d][%d]:\n",i,j);
scanf("%d",&a[i][j]);
if(a[i][j]<0||a[i][j]>8)
{
printf("WRONG DIGIT!!!");getch();
exit(0);
}
}
printf("/nplease wait...");
}
//******************************int h1()
{
int s=0,i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(a[i][j]==goal[i][j])
s++;
return s;
}
//******************************int h2()
{
int s,m,i,j,x,y;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(a[i][j]==goal[i][j])
s=0;
else
{
x=i,y=j;
while(a[i][j]!=goal[x][y])
{
x++;
if(x==3)
{
x=0;
y++;
}//end of if
if(y==3)
y=0;
}//end of while
s=(abs(x-i)+abs(y-j));
}//end of else
m+=s;
}//end of for(j)
return m;
}
//********************************void puzzle()
{
char next_move='h';int rh1,rh2,lh1,lh2,uh1,uh2,dh1,dh2,bh1,bh2;find_zero(  );
if(h1()==9)
output();
if(zero_j!=2&&pre_move!='l')
{
exchange(zero_i,zero_j,zero_i,zero_j+1);
rh1=h1();rh2=h2();next_move='r';
bh1=rh1;bh2=rh2;
exchange(zero_i,zero_j,zero_i,zero_j+1);
}
if(zero_j!=0&&pre_move!='r')
{
exchange(zero_i,zero_j,zero_i,zero_j-1);
lh1=h1();lh2=h2();
if(lh2<bh2||next_move=='h')
{
next_move='l';bh1=lh1;bh2=lh2;
}
exchange(zero_i,zero_j,zero_i,zero_j-1);
}
if(zero_i!=0&&pre_move!='d')
{
exchange(zero_i,zero_j,zero_i-1,zero_j);
uh1=h1();uh2=h2();
if(uh2<bh2||next_move=='h')
{
next_move='u';bh1=uh1;bh2=uh2;
}
exchange(zero_i,zero_j,zero_i-1,zero_j);
}
if(zero_i!=2&&pre_move!='u')
{
exchange(zero_i,zero_j,zero_i+1,zero_j);
dh1=h1();dh2=h2();
if(dh2<bh2||next_move=='h')
{
next_move='d';bh1=dh1;bh2=dh2;
}
exchange(zero_i,zero_j,zero_i+1,zero_j);
}
pre_move=next_move;
switch ((next_move)){
case'l':
exchange(zero_i,zero_j,zero_i,zero_j-1);
save_Q(next_move);
puzzle();
break;
case'r':
exchange(zero_i,zero_j,zero_i,zero_j+1);
save_Q(next_move);
puzzle();
break;
case'u':
exchange(zero_i,zero_j,zero_i-1,zero_j);
save_Q(next_move);
puzzle();
break;
case'd':
exchange(zero_i,zero_j,zero_i+1,zero_j);
save_Q(next_move);
puzzle();
break;
default:
printf("ERROR!!!");
exit(0);
}//end of switch
}//***********************************void output()
{
int i;
printf("\n");
for(i=0;i<=pop;i++)
printf("%c",stack[i]);
printf("\njob's done!!!");
getch();
exit(0);
}
//***********************************void save_Q(char c)
{
pop++;
if(pop==1000000)
{
printf("\nOVERFLOW!!!");
exit(0);
}
stack[pop]=c;
}
//***********************************
 :چشمک:

----------


## -Azure-

سلام به همه دوستان
یه سوال از خدمتون داشتم تو کتاب راسل در بخش توابع اکتشافی درباره پازل 8 گفته که تعداد حالات مجزای پازل 8 برابر 2/!9 یعنی 181440 حالت می خواستم بدونم این عدد چه جوری بدست میاد. تقسیم بر 2 از کجا اومده ؟ 

کسی اطلاعاتی درباره gaschnig's heuristic داره ؟
یه تابع اکتشافی برای مسئله پازل 8 هست

----------


## qwerty11

> ه سوال از خدمتون داشتم تو کتاب راسل در بخش توابع اکتشافی درباره پازل 8 گفته که تعداد حالات مجزای پازل 8 برابر 2/!9 یعنی 181440 حالت می خواستم بدونم این عدد چه جوری بدست میاد. تقسیم بر 2 از کجا اومده ؟


سلام. از اونجایی که از یه حالت اولیه فقط به نصف حالات ممکن میشه رفت.
اینجا درباره ی fifteen پازل توضیح داده ولی درباره ی پازل هشتایی هم صادقه.
http://en.wikipedia.org/wiki/Fifteen_puzzle

----------


## 13601360

> سلام. از اونجایی که از یه حالت اولیه فقط به نصف حالات ممکن میشه رفت.
> اینجا درباره ی fifteen پازل توضیح داده ولی درباره ی پازل هشتایی هم صادقه.
> http://en.wikipedia.org/wiki/Fifteen_puzzle


سلام دوست عزیز
"از اونجایی که از یه حالت اولیه فقط به نصف حالات ممکن میشه رفت" .چرا؟
براش اثبات ریاضی هم وجود داره

----------


## qwerty11

اون لینکی رو که گذاشتم ببینین توش درباره ی اینکه پازل چه وقت جواب داره نوشته.



> A simple parity argument shows that half of the starting positions for the _n_-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariant under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states.
>  The invariant is the parity of permutations of all 16 squares (15 pieces plus empty square) plus the parity of the taxicab distance moved by the empty square. This is an invariant because each move changes the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is not moved the permutation of the remaining pieces must be even. The same argument works for all rectangular boards, or more generally for all boards with no odd cycles.
>  The converse holds: all even permutations _are_ solvable,[1] but proofs of this result were hard to find in the mathematical literature (Israel Nathan Herstein and Irving Kaplansky even wrote in their _Matters Mathematical_ book that "No really easy proof seems to be known."), until Aaron F. Archer presented a short, simple, elementary proof, based on defining equivalence classes via a hamiltonian path.
>  For larger versions of the _n_-puzzle, finding a solution is easy, but the problem of finding the _shortest_ solution is NP-hard.[2] For the 15-puzzle, lengths of optimal solutions range from 0 to 80 moves; the 8-puzzle can be solved in 31 moves or fewer


اثبات ریاضی هم خوب مسلماً براش وجود داره اما من بلد نیستم.

اینم یه لینک دیگه برای تست کردن وجود جواب به همراه اثبات ریاضی : http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

----------


## Cancer

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


اگه میشه هدف ها فقط به جواب رسیدن نباشه، (که می دونم نیست).
به بهترین جواب رسیدن باشه.




با تشکر

----------


## Cancer

بهترین منبع برای معما 8
http://www.8puzzle.com
شک نکنین
که بهترینه

----------


## mehr_ara

دوستان کسی میتونه همین معمای هشت به روش a* رو با زبان سی شارپ بنویسه ... تو بعضی قسمتاش مشکل دارم

----------


## artasadeghi

این کد به چه روشی نوشته شده؟bfs?

----------


## artasadeghi

> #include<conio.h>
> #include<math.h>
> #include<stdio.h>
> #pragmahdrstop
> char pre_move;
> int a[3][3];
> int goal[3][3];
> int zero_i,zero_j;
> int stack[1000000];
> ...


این کد به په روشی نوشته شده؟(bfs??????????)

----------

