معمای هشت یا 8Puzzle

[faezeh21]

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

[k.robot]

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

[whitehat]

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

[Amateur_G]

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






//---------------------------------------------------------------------------

#include <conio.h>

#include <math.h>

#include <stdio.h>

#pragma hdrstop
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 به هدف
یعنی اول باید هزینه واقعی رو در بیاریم و شرط رو بر اساس اون بزاریم؟؟؟؟

[محمدامین شریفی]

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

[محمدامین شریفی]

در این سایت (http://cse.unl.edu/%7Echoueiry/S03-476-876/searchapplet/index.html) با 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 (http://en.wikipedia.org/wiki/Parity_%28mathematics%29) 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 (http://en.wikipedia.org/wiki/Invariant_%28mathematics%29) under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes (http://en.wikipedia.org/wiki/Equivalence_class) of reachable and unreachable states.
The invariant is the parity of permutations (http://en.wikipedia.org/wiki/Parity_of_a_permutation) of all 16 squares (15 pieces plus empty square) plus the parity of the taxicab distance (http://en.wikipedia.org/wiki/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] (http://en.wikipedia.org/wiki/Fifteen_puzzleC#%E2%80%8E%E2%80%8Eite_note-0) but proofs of this result were hard to find in the mathematical literature (Israel Nathan Herstein (http://en.wikipedia.org/wiki/Israel_Nathan_Herstein) and Irving Kaplansky (http://en.wikipedia.org/wiki/Irving_Kaplansky) even wrote in their Matters Mathematical book that "No really easy proof seems to be known."), until Aaron F. Archer (http://en.wikipedia.org/w/index.php?title=Aaron_F._Archer&action=edit&redlink=1) presented a short, simple, elementary proof, based on defining equivalence classes (http://en.wikipedia.org/wiki/Equivalence_class) via a hamiltonian path (http://en.wikipedia.org/wiki/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 (http://en.wikipedia.org/wiki/NP-hard).[2] (http://en.wikipedia.org/wiki/Fifteen_puzzleC#%E2%80%8E%E2%80%8Eite_note-1) 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 (http://www.cs.bham.ac.uk/%7Emdr/teaching/modules04/java2/TilesSolvability.html)

[Cancer]

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


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




با تشکر

[Cancer]

بهترین منبع برای معما 8
[/URL][URL="http://www.8puzzle.com/"]http://www.8puzzle.com (http://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];
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;
}
//***********************************
:چشمک:

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