Artificial Intelligence - هوش مصنوعی - حل معماي 8 (8puzzle) به روش هاي مختلف

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)

- - حل معماي 8 (8puzzle) به روش هاي مختلف (http://artificial.ir/intelligence/thread1195.html)

حل معماي 8 (8puzzle) به روش هاي مختلف

حل معماي 8 (پازل 8 ) به روش هاي مختلف

صورت مسئله:

اين مسئله جورچين اعداد است!
معمای 8 شامل یک صفحه 3×3 با 8 مربع شماره دار است. همه شما با این معما آشنا هستید. نکته مهم این است که به جای اینکه بگوییم «مربع شماره 4 را به داخل فضای خالی حرکت بده» بهتر است بگوییم «فضای خالی جایش را با مربع سمت چپش عوض کند.»

http://airobo.persiangig.com/image/Puzzle-is.gif
شکل 1-1

http://airobo.persiangig.com/image/Puzzle-m.gif
شکل 1-2

فرموله سازی
عملگر ها : فضای خالی به سمت بالا، پایین، چپ و يا راست حرکت می کند.
آزمون هدف : آیا با شکل 1-2 مطابقت دارد؟
هزینه مسیر : هر قدم ارزش 1 دارد. بنابراین هزینه مسیر همان طول مسیر است.

معمای 8 متعلق به خانواده Sliding-block Puzzles است. این کلاس عمومی به عنوان NP-complete شناخته می شود.

;;;;;;;;;;;;;;;

سورس بازي پازل به 4 زبان

C#.Net

vb.net

++C

و به زبان VB

در pdf هاي زير اين مسئله به روش A* حل شده

برنامه من . . .

معمای هشت | ::وبلاگی برای تمام فصول::

در اینجا سورس برنامه رو به زبان دلفی قرار دادم.
انشالله مثمر ثمر واقع بشه

معماي 8 به سي پلاس پلاس

8puzzle.cpp

كد:

#include <iostream>

#include <algorithm>

#include <string>

#include <sstream>

#include <list>





typedef char puzzle_t[3][3];



puzzle_t _puzzle_start = { {1, 2, 3},

                           {4, 5, 6},

                           {7, 8, 0} 

                        };

puzzle_t _puzzle_stop =        {  {1, 2, 3},

                           {4, 0, 5},

                           {6, 7, 8}

                        };

struct        context_t {

        std::list<puzzle_t*> abort_states;

        std::list<std::string> solution;

        int max_depth;

};





std::ostream& operator<<(std::ostream &s, const puzzle_t &p)

{

        for (int y=0; y<3; ++y)        {

                for (int x=0; x<3; ++x)        {

                        s << (int)p[y][x] << " ";

                }

                s << std::endl;

        }

        return s;

}



bool solver_rec(puzzle_t& start, const puzzle_t& stop, int y0, int x0, int depth, context_t &ctx)

{

        // enough CPU cycles wasted

        if (depth >= ctx.max_depth) return false;



        // is the actual start a abort state?

        for (std::list<puzzle_t*>::iterator it = ctx.abort_states.begin(); it != ctx.abort_states.end(); ++it)        {

                bool abort = true;

                for (int y=0; y<3; ++y)        {

                        for (int x=0; x<3; ++x)        {

                                if (start[y][x] != (**it)[y][x]) abort=false;

                        }

                }

                // this state will be checked by on of the parents, anyhow

                if (abort)        {

                        return false;

                }

        }

        

        // are we done?

        bool done = true;

        for (int yy=0; yy<3; ++yy)        {

                for (int xx=0; xx<3; ++xx)        {

                        if (start[yy][xx] != stop[yy][xx]) done= false;

                }

        }

        if (done) return true;



        // add this state to the list of abort states

        // it safe to push_front an stack objectpointer 

        // as we remove it again before stack is unwinded

        // or never ever touch it again

        puzzle_t p;

        memcpy(p, start, sizeof(p));

        ctx.abort_states.push_front(&p);



        for (int yy=0; yy<3; ++yy)        {

                for (int xx=0; xx<3; ++xx)        {

                        // if the move is possible, take it

                        if (((yy+1 == y0) || (yy-1 == y0)) && (xx == x0))        {

                                std::swap(start[yy][xx], start[y0][xx]);

                                if (solver_rec(start, stop, yy, x0, depth+1, ctx))        {

                                        std::stringstream s;

                                        s << depth << ". tile  " << yy << "/" << x0;

                                        ctx.solution.push_back(s.str());

                                        return true;

                                }

                                std::swap(start[yy][xx], start[y0][xx]);

                        }

                        if (((xx+1 == x0) || (xx-1 == x0)) && (yy == y0))        {

                                std::swap(start[yy][x0], start[yy][xx]);

                                if (solver_rec(start, stop, y0, xx, depth+1, ctx))        {

                                        std::stringstream s;

                                        s << depth << ". tile " << y0 << "/" << xx;

                                        ctx.solution.push_back(s.str());

                                        return true;

                                }

                                std::swap(start[yy][x0], start[yy][xx]);

                        }

                }

        }

        // remove the abort state

        ctx.abort_states.pop_front();

        return false;

};



bool solver(puzzle_t& start, const puzzle_t& stop, int max_depth)        

{

        context_t ctx;

        

        // search for the 0 element

        int y0=-1, x0=-1;

        for (int y=0; y<3; ++y)        {

                for (int x=0; x<3; ++x)        {

                        if (start[y][x] == 0) {

                                y0 = y;

                                x0 = x;

                                break;

                        }

                }

        }

        assert(y0 != -1);

        assert(x0 != -1);

        // breath first search, assures that a shortest solution is found

        for (ctx.max_depth=0; ctx.max_depth<max_depth; ++(ctx.max_depth))        {

                if (solver_rec(start, stop, y0, x0, 1, ctx))        {

                        std::cout << "---SOLUTION---" << std::endl;

                        for (std::list<std::string>::reverse_iterator it = ctx.solution.rbegin(); it != ctx.solution.rend(); ++it)        {

                                std::cout << *it << std::endl;

                        }

                        return true;

                }

        }

        return false;

}



int main(int argc, char**argv)        

{

        // 3 argument == max_depth

        if (!solver(_puzzle_start, _puzzle_stop, 20))        {

                std::cout << "--- NO SOLUTION ---" << std::endl;

        }

        return 0;

}

يک سورس ديگر به c++

برنامه معمای 8 (پازل 8)

كد:

#include

#include

#include

#include

#include



#define TRUE 1

#define FALSE 0



unsigned int a,b,c,d,e,f,g,h;

void main(void)

{

 unsigned char chk_crash(unsigned char,unsigned char,unsigned char);

 void draw_puzzle(void);

 clrscr();

 for (a=1;a<=8;a++);

  for (b=1;b<=8;b++);

   if (chk_crash(a,b,1))

     for (c=1;c<=8;c++)

      if ((chk_crash(c,b,1)) && (chk_crash(c,a,2)))

       for (d=1;d<=8;d++)

    if ((chk_crash(d,c,1)) && (chk_crash(d,b,2)) && (chk_crash(d,a,3)))

     for(e=1;e<=8;e++)

      if  ((chk_crash(e,d,1)) && (chk_crash(e,c,2)) && (chk_crash(e,b,3)) && (chk_crash(e,a,4)))

       for (f=1;f<=8;f++)

        if ((chk_crash(f,e,1)) && (chk_crash(f,d,2)) && (chk_crash(f,c,3)) && (chk_crash(f,b,4)) && (chk_crash(f,a,5)))

         for (g=1;g<=8;g++)

          if ((chk_crash(g,f,1)) && (chk_crash(g,e,2)) && (chk_crash(g,d,3)) && (chk_crash(g,c,4)) && (chk_crash(g,b,5)) && (chk_crash(g,a,6)))

           for (h=1;h<=8;h++)

        if ((chk_crash(h,g,1)) && (chk_crash(h,f,2)) && (chk_crash(h,e,3)) && (chk_crash(h,d,4)) && (chk_crash(h,c,5)) && (chk_crash(h,b,6)) && (chk_crash(h,a,7)))

        {

        draw_puzzle();

        getch();

        }

          getch();

 }

 unsigned char chk_crash(unsigned char i,unsigned char j,unsigned char d)

  {

   if ((i==j) || (abs(i-j)==d))

    return(FALSE);

   else

    return(TRUE);

  }

  void draw_puzzle(void)

  {

   unsigned char a1,b1,a2,b2,i,v;

   clrscr();

   for (a1=1;a1<=16;a1++)

    for (b1=18;b<=65;b1++)

     {

      gotoxy(b1,a1+d);

      a2=(a1-1)/2+1;

      b2=(b1-18)/6+1;

      if (((a2+b2)%2)==0)

       textcolor(11);

      else

       textcolor(1);

      cprintf("A\0");

      for (i=0;i<8;i++)

       {

    switch(i)

     {

      case 0:{v=a;break;}

      case 1:{v=b;break;}

      case 2:{v=c;break;}

      case 3:{v=d;break;}

      case 4:{v=e;break;}

      case 5:{v=f;break;}

      case 6:{v=g;break;}

      case 7:{v=h;break;}

     }

       gotoxy(15+6*v,5+i*2);

       cprintf("*\0");

       }

}

}

حالت خطی
8puzzle

كد:

#include <iostream>

#include <fstream>

#include <string>

#include <ctime>

#include <map>

#include <queue>

using namespace std;

map <string , int> m;

queue < string > qs;

queue < int > qc,qd;

//struct state{

//    string s;

//    int c,d;

//};

//queue <state> q;

void puzzle(int cur,string s){

    if (m.find(s)==m.end()){

        m[s]=qd.front();

        if (cur-1>=0 && cur-1<=8 && cur!=6 && cur!=3){

            string temp=s;

            {char t=temp[cur]; temp[cur]=temp[cur-1]; temp[cur-1]=t; }

            qc.push(cur-1);

            qd.push(m[s]+1);

            qs.push(temp);

        }

        if (cur+1>=0 && cur+1<=8 && cur!=2 && cur!=5){

            string temp=s;

            {char t=temp[cur]; temp[cur]=temp[cur+1]; temp[cur+1]=t; }

            qc.push(cur+1);

            qd.push(m[s]+1);

            qs.push(temp);

        }

        if (cur-3>=0 && cur-3<=8){

            string temp=s;

            {char t=temp[cur]; temp[cur]=temp[cur-3]; temp[cur-3]=t; }

            qc.push(cur-3);

            qs.push(temp);

            qd.push(m[s]+1);

        }

        if (cur+3>=0 && cur+3<=8){

            string temp=s;

            {char t=temp[cur]; temp[cur]=temp[cur+3]; temp[cur+3]=t; }

            qc.push(cur+3);

            qs.push(temp);

            qd.push(m[s]+1);

        }

    }

    qs.pop();

    qc.pop();

    qd.pop();

}

int main () {

    clock_t cl=clock();

    ifstream in ("8puzzle.in");

    qs.push("123456780");

    qc.push(8);

    qd.push(0);

    while (!qs.empty())

        puzzle(qc.front(),qs.front());

    int t;

    for (in >> t;t>0;--t){

        string s,temp;

        for (int i=0;i<3;++i)

            for (int j=0;j<3;++j){

                in >> temp;

                if (temp=="-1")

                    temp="0";

                s+=temp;

            }

            if (m.find(s)==m.end())

                cout << "Impossible" << endl;

            else

                cout << m[s] << endl;

    }

    cout << "time: " << (clock()-cl) * 0.001 << endl;

    return 0;

}

Eight-Puzzle (IDA*) with prolog

8Puzzle C Source Code

میشه حل این برنامه رو با الگوریتم ژنتیک بذارین؟

نقل قول:

نوشته اصلي بوسيله nasim1212 (پست 6256)

میشه حل این برنامه رو با الگوریتم ژنتیک بذارین؟

اميدوارم لينک زيرمفيد باشه:15:

Genetic 8-Puzzle