نمایش نتایج 1 تا 20 از 20

نام تاپیک: معمای هشت یا 8Puzzle

  1. #1

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

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


  2. #2
    کاربر جدید آواتار k.robot
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    ارومیه
    پست
    24
    از *A با هیوریستیک مانهاتانی استفاده کن .تو کتاب هوش مصنوعی راسل فصل 4 توضیح داده شده.

  3. #3
    مدیر بخش آواتار whitehat
    تاریخ عضویت
    مهر 1382
    محل زندگی
    شیراز
    پست
    2,175
    ظاهرا لینک ها Expire شده من دو PDF برای حل این مسئله در اینجا قرار می دهم.
    توجه کنید که این مسئله به روش A* حل شده. در ضمن برای PDF دوم شما باید در مورد فاصله مانهاتان اطلاعات داشته باشید
    فایل های ضمیمه فایل های ضمیمه
    To follow the path:
    Look to the master
    Follow the master
    Walk with the master
    See through the master
    Become the master

  4. #4

    Lightbulb نقل قول: معمای هشت یا 8Puzzle

    سلام.
    اگه يكم بهم ريخته يا كمي درهمه ببخشيد.فرست نشد مرتبش كنم.
    من براي محاسبه هزينه مسير دو مورد در نظر گرفتم:
    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;
    }

    //***********************************
    اميدوارم مفيد باشه .

  5. #5
    منتظر تایید آدرس ایمیل
    تاریخ عضویت
    شهریور 1387
    محل زندگی
    کرمانشاه
    پست
    16

    نقل قول: معمای هشت یا 8Puzzle

    جناب Amateur_G از روش A* استفاده کردین؟
    آخرین ویرایش به وسیله MIDOSE : جمعه 11 دی 1388 در 14:31 عصر دلیل: فونت نامناسب

  6. #6
    منتظر تایید آدرس ایمیل
    تاریخ عضویت
    شهریور 1387
    محل زندگی
    کرمانشاه
    پست
    16

    نقل قول: معمای هشت یا 8Puzzle

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

  7. #7
    کاربر دائمی آواتار محمدامین شریفی
    تاریخ عضویت
    شهریور 1386
    محل زندگی
    تهران - شیراز
    پست
    1,302

    نقل قول: معمای هشت یا 8Puzzle

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

  8. #8
    کاربر دائمی آواتار محمدامین شریفی
    تاریخ عضویت
    شهریور 1386
    محل زندگی
    تهران - شیراز
    پست
    1,302

    نقل قول: معمای هشت یا 8Puzzle

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

  9. #9

    نقل قول: معمای هشت یا 8Puzzle

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

  10. #10
    کاربر دائمی
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    پست
    227

    Smile نقل قول: معمای هشت یا 8Puzzle

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

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

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

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

  11. #11

    نقل قول: معمای هشت یا 8Puzzle


    #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;
    }
    //***********************************

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

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

  13. #13
    کاربر دائمی
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    پست
    227

    نقل قول: معمای هشت یا 8Puzzle

    ه سوال از خدمتون داشتم تو کتاب راسل در بخش توابع اکتشافی درباره پازل 8 گفته که تعداد حالات مجزای پازل 8 برابر 2/!9 یعنی 181440 حالت می خواستم بدونم این عدد چه جوری بدست میاد. تقسیم بر 2 از کجا اومده ؟
    سلام. از اونجایی که از یه حالت اولیه فقط به نصف حالات ممکن میشه رفت.
    اینجا درباره ی fifteen پازل توضیح داده ولی درباره ی پازل هشتایی هم صادقه.
    http://en.wikipedia.org/wiki/Fifteen_puzzle

  14. #14
    کاربر دائمی آواتار 13601360
    تاریخ عضویت
    آذر 1386
    محل زندگی
    کنار دریای خزر
    پست
    422

    نقل قول: معمای هشت یا 8Puzzle

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

  15. #15
    کاربر دائمی
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    پست
    227

    نقل قول: معمای هشت یا 8Puzzle

    اون لینکی رو که گذاشتم ببینین توش درباره ی اینکه پازل چه وقت جواب داره نوشته.
    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

  16. #16
    کاربر دائمی آواتار Cancer
    تاریخ عضویت
    شهریور 1388
    محل زندگی
    <include <Cancer.h#
    پست
    135

    نقل قول: معمای هشت یا 8Puzzle

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


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




    با تشکر

  17. #17
    کاربر دائمی آواتار Cancer
    تاریخ عضویت
    شهریور 1388
    محل زندگی
    <include <Cancer.h#
    پست
    135

    نقل قول: معمای هشت یا 8Puzzle

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

  18. #18

    نقل قول: معمای هشت یا 8Puzzle

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

  19. یک شنبه 26 آبان 1392, 13:09 عصر


  20. #19

    نقل قول: معمای هشت یا 8Puzzle

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

  21. #20

    نقل قول: معمای هشت یا 8Puzzle

    نقل قول نوشته شده توسط 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;
    }
    //***********************************
    این کد به په روشی نوشته شده؟(bfs??????????)

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •