الگوريتم مربع هشت ( 8-puzzle )

[Y@SiN]

مربع هشت ( 8-puzzle )


http://pnu-club.com/imported/mising.jpg

در یک مربع 3 در 3 که شامل 9 خانه کوچک است ، هشت مربع شماره گذاری شده قرار داده ایم . یکی از خانه ها نیز خالی است . مسئله با یک حالت اولیه شروع می شود . هدف چیدن مربع های شماره گذاری شده به ترتیب روبرو است ( حالت هدف ) :


http://pnu-club.com/imported/mising.jpg


نکته مسئله مربع هشت اینسنت که فقط مربع های اطراف خانه خالی را می توانیم با خانه خالی تعویض کنیم . یعنی با حرکت دادن مکرر خانه خالی به چپ ، راست ، بالا و پایین باید به حالت هدف برسیم . برای حل این مساله می توان از روش جستجوی A* استفاده کرد . برای این مسئله چند هیوریستیک مختلف وجود دارد . دو هیوریستیک معمول به صوزت زیر هستند :
1) هیوریستیک اول سعی می کند خانه خالی را طوری جابجا کند که تعداد مربع هایی را در خانه خود قرار نگرفته اند ، صفر شود . یعنی این هیوریستیک بر اساس تعداد مربع هایی که در خانه خود قرار نگرفته اند ، جستجو انجام می دهد.

2) هیوریستیک دوم مجموع فاصله های بلوک شهری هر مربع از خانه خود را محاسبه کرده و سعی می کند خانه حالی را طوری حرکت دهد که این مقدار را به صفر برسد .

[far.farzane]

سلام
کد الگوریتم مربوط به پازل 8 تایی را قرار میدهید؟
با تشکر

[sunyboy]

سلام
کد الگوریتم مربوط به پازل 8 تایی را قرار میدهید؟
با تشکر



بفرمایید




/*
Solution of the 8 puzzle.
Uses A-Star algorithm.
*/
#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#define DOWN 0
#define UP 1
#define LEFT 2
#define RIGHT 3
#define H2
struct elementstruct
{
int block[9];
char* str;
int pathcost;
int valid;
int totalcost;
elementstruct* next;
};
int heur(int block[]);
void prepend(elementstruct* newnode, elementstruct* oldnode, int operator1);
int goal(int* block);
int notonqueue(int block[]);
elementstruct* bestnodefromqueue();
void print_block(int* block);
int apply (int* newstate, int* oldstate, int op);
elementstruct* newelement();
int op(char);
char to_char(int i);
char rep[] = "dulr";
int notvalid1[4] = { 6, 0, 0, 2 };
int notvalid2[4] = { 7, 1, 3, 5 };
int notvalid3[4] = { 8, 2, 6, 8 };
int applyparam[4] = { +3, -3, -1, +1 };
int goal_block[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8}; //8 indicates no tile
int maxdepth;
elementstruct* top;
int main()
{
int block[9];
printf("\nThe Eight Puzzle!\n");
printf("\nPlease Enter the initial state of the game \n"
" [Represent tiles with numbers 1 to 8, and the blank space as 'x'.\n"
" Start writing them from left to right for each row. Start from the topmost row to the bottommost row.\n"
" Your final string will look similar to this '1 4 2 3 x 6 7 8 5'.\n"
" Do not forget the spaces in between the characters]\n");
int i = 0;
while(i<9)
{
char chr;
chr = fgetc(stdin);
if (chr==32) continue;
if (chr=='x') block[i] = 8;
else if (chr >= '1' && chr <= '9') block[i] = chr - '1';
else { printf("Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.", chr); return 1; }
i++;
}
fgetc(stdin); //flush out the end of line character
printf("\n Now Enter the Goal State in a similar way. (Typical. 1 2 3 4 5 6 7 8 x): ");
i = 0;
while(i<9)
{
char chr;
chr = fgetc(stdin);
if (chr==32) continue;
if (chr=='x') goal_block[i] = 8;
else if (chr >= '1' && chr <= '9') goal_block[i] = chr - '1';
else { printf("chr=%d. Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.",(int) chr); return 1; }
i++;
}
printf("Enter the maximum depth you want to search (<25 is solved quickly): ");
scanf("%d", &maxdepth);
printf("\nWorking...");
top = newelement();
for(i=0; i<9; i++)
top->block[i] = block[i];
top->totalcost = heur(block);

elementstruct* newnode = newelement();
while (1)
{
elementstruct* node = bestnodefromqueue();
if (node == NULL) {
printf("done!\n");
printf("There is no solution to this of less than %d depth.\n", maxdepth);
printf("Try increasing the depth by 5.\n");
printf("If there is no solution within 35-40 depth, the pattern is usually unsolvable.\n\n");
break;
}
else if (goal(node->block)) {
char chr[15];
printf("done. \nFound the solution of least number of steps (%d).", node->pathcost);
printf("\nWant a graphical display of each step? (Y/N)?");
scanf("%s", chr);
if(chr[0] =='n' || chr[0]=='N') {
printf("\n (Move Blank u=up, d=down, l=left, r=right)\n");
printf(node->str);
printf("\n");
break;
}

int block2[9];
for (i=0; i<node->pathcost; i++)
{
print_block(block);
apply(block2, block, op(node->str[i]));
for(int j=0; j<=8; j++)
block[j] = block2[j];
}
print_block(block);

printf("\nGraphical Display Complete.\nThe steps taken were: (Move blank u=up, d=down, l-left, r=right)\n");
printf(node->str);
printf("\n");
break;

}
if (node->totalcost > maxdepth) continue;
for(i=0; i<=3; i++) {
if (apply(newnode->block, node->block, i) == -1)
continue;
if (notonqueue(newnode->block)) {
prepend(newnode, node, i);
newnode = newelement();
if (newnode==NULL) { printf ("ERROR!! insufficient memory!! Try decreasing depth!"); return 1; }
}
}
}
return 0;
}
int heur(int* block)
{
#ifdef H2
int to_return = 0;
for(int i=0; i<9; i++)
{
to_return += abs((i/3) - (block[i]/3));
to_return += abs((i%3) - (block[i]%3));
}
return to_return;

#else
int to_return = 0;
for(int i=0; i<9; i++)
{
if (block[i] != i) to_return++;
}
return to_return;

#endif
}
void prepend(elementstruct* newnode, elementstruct* oldnode, int op)
{
newnode->next = top;
top = newnode;
strcpy(newnode->str, oldnode->str);
newnode->str[oldnode->pathcost] = rep[op];
newnode->str[oldnode->pathcost+1] = 0;
newnode->pathcost = oldnode->pathcost+1;
newnode->totalcost = newnode->pathcost + heur(newnode->block);
if (newnode->totalcost < oldnode->totalcost) newnode->totalcost = oldnode->totalcost;
}
int goal(int* block)
{
int* g_block = goal_block;
for(int i=0; i<9; i++)
if ((*(block++))!=(*(g_block++)))
return 0;
return 1;
}
int notonqueue(int* block)
{
int i,j;
elementstruct* t = top;

while (t!=NULL)
{
for(i=0; i<9; i++)
if (t->block[i] != block[i]) break;
if (i==9) return 0;

t = t->next;
}
return 1;
}
elementstruct* bestnodefromqueue()
{
elementstruct* t = top;
int min_totalpathcost = 1000;
int totalpathcost;
elementstruct* to_return = NULL;
while (t != NULL)
{
if (t->valid==1 && t->totalcost < min_totalpathcost)
{
min_totalpathcost = t->totalcost;
to_return = t;
}
t = t->next;
}

if (to_return != NULL) to_return->valid = 0;
return to_return;
}
int apply (int* newstate, int* oldstate, int op)
{
int j;
int blank;
for (j=0; j<9; j++)
if (oldstate[j]==8) { blank=j; break; }
if (blank==notvalid1[op] || blank==notvalid2[op] || blank==notvalid3[op])
return -1;
for (j=0; j<9; j++)
newstate[j] = oldstate[j];
newstate[blank] = newstate[blank+applyparam[op]];
newstate[blank+applyparam[op]] = 8;
return 1;
}
elementstruct* newelement()
{
elementstruct* t = new elementstruct;
if (t==NULL) return NULL;
t->valid = 1;
t->str = new char[maxdepth+1];
if (t->str ==NULL) return NULL;
t->str[0] = 0;
t->pathcost = t->totalcost = 0;
t->next = NULL;
return t;
}
void print_block(int* block)
{
printf("\n");
printf ("\n-------");
printf ("\n|%c|%c|%c|", to_char(block[0]), to_char(block[1]), to_char(block[2]));
printf ("\n-------");
printf ("\n|%c|%c|%c|", to_char(block[3]), to_char(block[4]), to_char(block[5]));
printf ("\n-------");
printf ("\n|%c|%c|%c|", to_char(block[6]), to_char(block[7]), to_char(block[8]));
printf ("\n-------");
}
char to_char(int i)
{
if (i>=0 &&i<=7) return i+'1';
else if (i==8) return 'x';
else { printf("ERROR in Program!"); return -1; }
}
int op(char i)
{
switch (i)
{
case 'd': return 0;
case 'u': return 1;
case 'l': return 2;
case 'r': return 3;
default: printf("ERROR!"); return -1;
}
}

[far.farzane]

سلام
خیلی خیلی ممنونم:36:

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

[far.farzane]

سلام
خیلی خیلی ممنونم:36:

[far.farzane]

سلام
امکانش هست شبه کد یا ایده حل 8پازل را به روش عمقی تدریجی بگذارید؟

[marg8742]

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

[Borna66]

با سلام

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

موفق باشید

روزگار خوش

[shima_70]

سلام
خسته نباشید

ببخشید میتونه کسی بگ الان این برنامه ای ک انیجا نوشتین براساس کدوم هیستوریک هس؟؟

ی کمم درباره این الگوریتم توضیح بدین من گیج شدم!!

ممنون میشم ی کم کمک کنید.

[mahshad.]

سلام
خسته نباشید

ببخشید میتونه کسی بگ الان این برنامه ای ک انیجا نوشتین براساس کدوم هیستوریک هس؟؟

ی کمم درباره این الگوریتم توضیح بدین من گیج شدم!!

ممنون میشم ی کم کمک کنید.

فکر کنم عمقی محدود باشه.