Artificial Intelligence - هوش مصنوعی

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)
-   حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)
-   -   حل معماي 8 (8puzzle) به روش هاي مختلف (http://artificial.ir/intelligence/thread1195.html)

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۲:۳۸ بعد از ظهر

حل معماي 8 (8puzzle) به روش هاي مختلف
 
5(ها)ضميمه
حل معماي 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

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۲:۵۳ بعد از ظهر

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

maskofgod ۱۰-۱۱-۱۳۸۸ ۰۵:۱۹ بعد از ظهر

برنامه من . . .
 
1(ها)ضميمه
معمای هشت | ::وبلاگی برای تمام فصول::

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

Astaraki ۱۲-۲۵-۱۳۸۸ ۱۱:۵۴ قبل از ظهر

معماي 8 به سي پلاس پلاس
 
1(ها)ضميمه
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++

Astaraki ۱۲-۲۵-۱۳۸۸ ۱۲:۰۶ بعد از ظهر

برنامه معمای 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");
      }
}
}


Astaraki ۱۲-۲۵-۱۳۸۸ ۱۲:۳۲ بعد از ظهر

حالت خطی
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;
}


Astaraki ۰۳-۸-۱۳۸۹ ۱۱:۱۰ قبل از ظهر

1(ها)ضميمه
Eight-Puzzle (IDA*) with prolog

Astaraki ۰۳-۸-۱۳۸۹ ۱۱:۴۴ قبل از ظهر

1(ها)ضميمه
8Puzzle C Source Code

nasim1212 ۰۳-۱۲-۱۳۸۹ ۱۱:۳۶ بعد از ظهر

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

Astaraki ۰۳-۱۳-۱۳۸۹ ۱۱:۰۶ قبل از ظهر

نقل قول:

نوشته اصلي بوسيله nasim1212 (پست 6256)
میشه حل این برنامه رو با الگوریتم ژنتیک بذارین؟


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

Genetic 8-Puzzle

Astaraki ۰۳-۱۳-۱۳۸۹ ۰۴:۰۶ بعد از ظهر

Genetic algorithm on 8-puzzle problem
 
1(ها)ضميمه
كد براي حل مسثله معماي 8 به روش الگوريتم ژنتيك
:25:
اين برنامه خيلي ابتدايي بوده و جنبه آموزشي دارد.
در محيط MC++ بوده و نتيجه را در محيط console ارائه مي كند .
برنامه تلاش مي كند تا با كمترين حركات ممكن از حالت اوليه به حالت نهايي برسد و در صورت موجود بودن يك راه بين دو حالت دنباله حركت ها را ارائه مي دهد و در غير اينصورت كمترين فاصله ي "منهتن"(manhattan) ممكن بين دو حالت را ارائه مي كند .
اين برنامه به صورت كد باز در اينجا ارئه مي شود و هر كسي با ديد آموزشي مجاز به تغيير و شير آن مي باشد .
تولید کننده: رامين شكري كلان

green_Dream ۰۳-۲۴-۱۳۸۹ ۰۸:۲۴ بعد از ظهر

با سلام

خواهشا،ملتمسانه اگر كسي از دوستان گرامي ، معماي 8 پازل رو به روشهاي A*,*IDA,greedy search , BFS به زبان C#داره تو فروم بذاره

mardin200 ۰۳-۲۴-۱۳۸۹ ۰۸:۵۱ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله green_Dream (پست 6502)
با سلام

خواهشا،ملتمسانه اگر كسي از دوستان گرامي ، معماي 8 پازل رو به روشهاي A*,*IDA,greedy search , BFS به زبان C#داره تو فروم بذاره

دوست عزیز در این تاپیک قرار داده شده
امیدوارم بدردتون بخوره

محمد شمس ۰۳-۲۵-۱۳۸۹ ۰۷:۲۰ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله reyhane (پست 6265)
اميدوارم لينک زيرمفيد باشه:15:

genetic 8-puzzle

سلام


زمان مورد نیاز آن برای حل، خیلی زیاد است. در واقع اصلا بهینه نیست.

green_Dream ۰۴-۲۲-۱۳۸۹ ۰۲:۱۳ بعد از ظهر

با سلام و احترام

بينهايت ممنون ميشم اگه درمورد شبه كد يا سورس برنامه 8پازل به روش حريصانه و ida*توضيح دهيدچون روشهاي ديگر جستجو براي مطالعه و فهم دقيق به وفور در اينترنت يافت ميشود ولي هيچ سايتي درباره اين دو روش چيزي ننوشته اند

با تشكر

Astaraki ۰۵-۲۰-۱۳۸۹ ۱۰:۱۰ قبل از ظهر

به زبان جاوا
 
Solution of the 8-puzzle using iterative deepening A* (IDA*) search

كد:

/*
        Author:        James Pate Williams, Jr.

        Solution of 8-puzzle using IDA* search
*/

import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class Puzzle8IPanel extends JPanel {
        char[] s;
        int deltaX, deltaY;
        int x0, x1, y0, y1;
       
        public Puzzle8IPanel(int iWidth, int iHeight, char[] solution) {
                x0 = iWidth / 8;
                x1 = 7 * x0;
                y0 = iHeight / 8;
                y1 = 7 * y0;
                deltaX = (x1 - x0) / 3;
                deltaY = (y1 - y0) / 3;
                s = new char[9];
                s = solution;
        }
       
        public void sevenSegmentDisplay(Graphics g, char digit,
                int x, int y, int xUnit, int yUnit) {
                int xInc = xUnit / 10;
                int yInc = yUnit / 10;
                int xPoint1 = x + xInc;
                int yPoint1 = y + yInc;
                int xPoint2 = x + xUnit - xInc;
                int yPoint2 = yPoint1;
                int xPoint3 = xPoint1;
                int yPoint3 = y + yUnit / 2;
                int xPoint4 = xPoint2;
                int yPoint4 = yPoint3;
                int xPoint5 = xPoint3;
                int yPoint5 = y + yUnit - yInc;
                int xPoint6 = xPoint4;
                int yPoint6 = yPoint5;

                g.setColor(Color.white);
                switch (digit) {
                        case '0':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
                                g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
                                g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
                                break;
                        case '1':
                                g.drawLine(xPoint1, yPoint1, xPoint5, yPoint5);
                                break;
                        case '2':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
                                g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
                                g.drawLine(xPoint3, yPoint3, xPoint5, yPoint5);
                                g.drawLine(xPoint5, yPoint5, xPoint6, yPoint6);
                                break;
                        case '3':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
                                g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
                                g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
                                g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
                                break;
                        case '4':
                                g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
                                g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
                                g.drawLine(xPoint4, yPoint4, xPoint2, yPoint2);
                                g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
                                break;
                        case '5':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
                                g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
                                g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
                                g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
                                break;
                        case '6':
                                g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
                                g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
                                g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
                                g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
                                g.drawLine(xPoint5, yPoint5, xPoint3, yPoint3);
                                break;
                        case '7':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
                                break;
                        case '8':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
                                g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
                                g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
                                g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
                                break;
                        case '9':
                                g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
                                g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
                                g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
                                g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
                                break;
                }
        }               
                                 
        public void paintComponent(Graphics g) {
                int i, j, x, y;
                  int xUnit = deltaY / 9;
                  int yUnit = deltaY / 15;
               
                super.paintComponent(g);
                y = y0;
                for (i = 0; i < 3; i++) {
                        x = x0;
                        for (j = 0; j < 3; j++) {
                                g.setColor(Color.white);
                                g.drawRect(x, y, deltaX, deltaY);
                                g.setColor(Color.black);
                                g.fillRect(x, y, deltaX, deltaY);
                                sevenSegmentDisplay(g, s[3 * i + j], x, y, deltaX, deltaY);
                                x += deltaX;
                        }
                        y += deltaY;
                }               
        }

        public void setSolution(char[] solution) {
                s = new char[9];
                s = solution;
        }
}

class Puzzle8IFrame extends JFrame implements Runnable {
        boolean next;
        int iHeight, iWidth;
        JButton jButton1 = new JButton();
        JPanel jPanel = new JPanel();
        BorderLayout borderLayout = new BorderLayout();
        Puzzle8IPanel puzzle8IPanel;
       
        // step 3 - percentage size the window
        void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
                Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
                iWidth = screen.width * wPerc / 100;
                iHeight = screen.height * hPerc / 100;
                frame.setSize(iWidth, iHeight);
        }
       
        // step 4 - center the window
        void centerOnScreen(JFrame frame) {
                Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
                Dimension window = frame.getSize();
                int iCenterX = screen.width / 2;
                int iCenterY = screen.height / 2;
                frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
        }
       
        public Puzzle8IFrame(char[] solution) {
                String title = "Puzzle8I by James Pate Williams, Jr. (c) 2001";
                next = false;
                jButton1.setToolTipText("Perform one iteration of algorithm");
                jButton1.setText("Next");
                jButton1.setVerticalAlignment(SwingConstants.BOTTOM);
                jButton1.addActionListener(new java.awt.event.ActionListener() {
                        public void actionPerformed(ActionEvent e) {
                                jButton1_actionPerformed(e);
                        }
                    });
                    this.getContentPane().setLayout(borderLayout);
                setTitle(title);
                addWindowListener(new WindowAdapter() {
                        public void windowClosing(WindowEvent event) {
                                System.exit(0);
                        }
                });
                setDesktopSize(this, 100, 100);
                centerOnScreen(this);
                Container contentPane = getContentPane();
                contentPane.add(jPanel, BorderLayout.SOUTH);
                jPanel.add(jButton1, BorderLayout.CENTER);
                puzzle8IPanel = new Puzzle8IPanel(iWidth, iHeight, solution);
                contentPane.add(puzzle8IPanel, BorderLayout.CENTER);
                this.show();
                (new Thread(this)).run();
        }

        public boolean getNext() {
                return next;
        }

        public void setNext(boolean n) {
                next = n;
        }

        void jButton1_actionPerformed(ActionEvent e) {
                next = true;
        }
       
        public void run() {
                Thread.yield();
        }

        public void draw(char[] solution) {
                puzzle8IPanel.setSolution(solution);
                puzzle8IPanel.paintComponent(getGraphics());
        }
}

class PuzzleI {
        int flag, g, moves, nodesExpanded;
        int[][] board;
        Date date;
        Random random;
        public static final int Infinity = 2000000000;
        public static final int MaxMoves = 100;

        public PuzzleI() {
                boolean found;
                int digit, i, j, k;
                int[] placed = new int[9];
               
                date = new Date();
                random = new Random(date.getTime());
                for (i = 0; i < 9; i++)
                        placed[i] = 0;
                board = new int[3][3];
                g = moves = nodesExpanded = 0;
                for (i = 0; i < 3; i++)
                        for (j = 0; j < 3; j++)
                                board[i][j] = 0;
                for (i = 0; i < 9; i++) {
                        found = false;
                        do {
                                digit = random.nextInt(9);
                                found = placed[digit] == 0;
                                if (found)
                                        placed[digit] = 1;
                        } while (!found);
                        do {
                                j = random.nextInt(3);
                                k = random.nextInt(3);
                                found = board[j][k] == 0;
                                if (found)
                                        board[j][k] = digit;
                        } while (!found);
                }
        }

        int getNodesExpanded() {
                return nodesExpanded;
        }

        int expand(int[][] square, int[][][] tempSquare) {
                int b = - 1, col = - 1, i, j, k, row = - 1;

                for (i = 0; i < 4; i++)
                        for (j = 0; j < 3; j++)
                                for (k = 0; k < 3; k++)
                                        tempSquare[i][j][k] = square[j][k];
                for (i = 0; i < 3; i++) {
                        for (j = 0; j < 3; j++) {
                                if (square[i][j] == 0) {
                                        row = i;
                                        col = j;
                                        break;
                                }
                        }
                }
                if (row == 0 && col == 0) {
                        tempSquare[0][0][0] = tempSquare[0][0][1];
                        tempSquare[0][0][1] = 0;
                        tempSquare[1][0][0] = tempSquare[1][1][0];
                        tempSquare[1][1][0] = 0;
                        b = 2;
                }
                else if (row == 0 && col == 1) {
                        tempSquare[0][0][1] = tempSquare[0][0][0];
                        tempSquare[0][0][0] = 0;
                        tempSquare[1][0][1] = tempSquare[1][1][1];
                        tempSquare[1][1][1] = 0;
                        tempSquare[2][0][1] = tempSquare[2][0][2];
                        tempSquare[2][0][2] = 0;
                        b = 3;
                }
                else if (row == 0 && col == 2) {
                        tempSquare[0][0][2] = tempSquare[0][0][1];
                        tempSquare[0][0][1] = 0;
                        tempSquare[1][0][2] = tempSquare[1][1][2];
                        tempSquare[1][1][2] = 0;
                        b = 2;
                }
                else if (row == 1 && col == 0) {
                        tempSquare[0][1][0] = tempSquare[0][0][0];
                        tempSquare[0][0][0] = 0;
                        tempSquare[1][1][0] = tempSquare[1][1][1];
                        tempSquare[1][1][1] = 0;
                        tempSquare[2][1][0] = tempSquare[2][2][0];
                        tempSquare[2][2][0] = 0;
                        b = 3;
                }
                else if (row == 1 && col == 1) {
                        tempSquare[0][1][1] = tempSquare[0][1][0];
                        tempSquare[0][1][0] = 0;
                        tempSquare[1][1][1] = tempSquare[1][0][1];
                        tempSquare[1][0][1] = 0;
                        tempSquare[2][1][1] = tempSquare[2][1][2];
                        tempSquare[2][1][2] = 0;
                        tempSquare[3][1][1] = tempSquare[3][2][1];
                        tempSquare[3][2][1] = 0;
                        b = 4;
                }
                else if (row == 1 && col == 2) {
                        tempSquare[0][1][2] = tempSquare[0][0][2];
                        tempSquare[0][0][2] = 0;
                        tempSquare[1][1][2] = tempSquare[1][1][1];
                        tempSquare[1][1][1] = 0;
                        tempSquare[2][1][2] = tempSquare[2][2][2];
                        tempSquare[2][2][2] = 0;
                        b = 3;
                }
                else if (row == 2 && col == 0) {
                        tempSquare[0][2][0] = tempSquare[0][1][0];
                        tempSquare[0][1][0] = 0;
                        tempSquare[1][2][0] = tempSquare[1][2][1];
                        tempSquare[1][2][1] = 0;
                        b = 2;
                }
                else if (row == 2 && col == 1) {
                        tempSquare[0][2][1] = tempSquare[0][2][0];
                        tempSquare[0][2][0] = 0;
                        tempSquare[1][2][1] = tempSquare[1][1][1];
                        tempSquare[1][1][1] = 0;
                        tempSquare[2][2][1] = tempSquare[2][2][2];
                        tempSquare[2][2][2] = 0;
                        b = 3;
                }
                else if (row == 2 && col == 2) {
                        tempSquare[0][2][2] = tempSquare[0][2][1];
                        tempSquare[0][2][1] = 0;
                        tempSquare[1][2][2] = tempSquare[1][1][2];
                        tempSquare[1][1][2] = 0;
                        b = 2;
                }
                return b;
        }

        int heuristic(int[][] square) {
                return ManhattenDistance(square);
        }
       
        int DFSContour(char[][] solution, int fLimit, int m, int[][] board) {
                boolean equal, skip;
                char[] tempSolution = new char[9];       
                int b, count, fCost, i, j, k, l, n, newF, nextF = Infinity;
                int[][][] tempSquare = new int[4][3][3];

                fCost = g + heuristic(board);
                for (i = k = 0; i < 3; i++)
                        for (j = 0; j < 3; j++)
                                solution[m][k++] = (char) (board[i][j] + '0');
                m++;
                if (m == MaxMoves)
                        return Infinity;
                if (fCost > fLimit) {
                        flag = 0;
                        return fCost;
                }
                if (board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 &&
                        board[1][0] == 8 && board[1][1] == 0 && board[1][2] == 4 &&
                        board[2][0] == 7 && board[2][1] == 6 && board[2][2] == 5) {
                        flag = 1;
                        moves = m;
                        return fCost;
                }
                b = expand(board, tempSquare);
                nodesExpanded += b;
                for (i = 0; i < b; i++) {
                        skip = false;
                        for (j = m - 1; !skip && j < m; j++) {
                                for (k = l = 0; k < 3; k++)
                                        for (n = 0; n < 3; n++)
                                                tempSolution[l++] = (char) (tempSquare[i][k][n] + '0');
                                equal = tempSolution[0] == solution[j][0];
                                for (k = 1; equal && k < 9; k++)
                                        equal = tempSolution[k] == solution[j][k];
                                if (equal)
                                        skip = true;
                        }
                        if (!skip) {
                                newF = DFSContour(solution, fCost, m, tempSquare[i]);
                                if (flag == 1)
                                        return newF;
                                nextF = newF < nextF ? newF : nextF;
                        }
                }
                g++;
                return nextF;
        }

        int outOfPlace(int[][] square) {
                int i, j, oop = 0;
                int[][] goal = new int[3][3];
               
                goal[0][0] = 1;
                goal[0][1] = 2;
                goal[0][2] = 3;
                goal[1][0] = 8;
                goal[1][1] = 0;
                goal[1][2] = 4;
                goal[2][0] = 7;
                goal[2][1] = 6;
                goal[2][2] = 5;
                for (i = 0; i < 3; i++)
                        for (j = 0; j < 3; j++)
                                if (square[i][j] != goal[i][j])
                                        oop++;
                return oop;
        }

        int ManhattenDistance(int[][] square) {
                // city block or Manhatten distance heuristic
                int md = 0;

                if (square[0][0] == 1)
                        md += 0;
                else if (square[0][0] == 2)
                        md += 1;
                else if (square[0][0] == 3)
                        md += 2;
                else if (square[0][0] == 4)
                        md += 3;
                else if (square[0][0] == 5)
                        md += 4;
                else if (square[0][0] == 6)
                        md += 3;
                else if (square[0][0] == 7)
                        md += 2;
                else if (square[0][0] == 8)
                        md += 1;
                if (square[0][1] == 1)
                        md += 1;
                else if (square[0][1] == 2)
                        md += 0;
                else if (square[0][1] == 3)
                        md += 1;
                else if (square[0][1] == 4)
                        md += 2;
                else if (square[0][1] == 5)
                        md += 3;
                else if (square[0][1] == 6)
                        md += 2;
                else if (square[0][1] == 7)
                        md += 3;
                else if (square[0][1] == 8)
                        md += 2;
                if (square[0][2] == 1)
                        md += 2;
                else if (square[0][2] == 2)
                        md += 1;
                else if (square[0][2] == 3)
                        md += 0;
                else if (square[0][2] == 4)
                        md += 1;
                else if (square[0][2] == 5)
                        md += 2;
                else if (square[0][2] == 6)
                        md += 3;
                else if (square[0][2] == 7)
                        md += 4;
                else if (square[0][2] == 8)
                        md += 3;
                if (square[1][0] == 1)
                        md += 1;
                else if (square[1][0] == 2)
                        md += 2;
                else if (square[1][0] == 3)
                        md += 3;
                else if (square[1][0] == 4)
                        md += 2;
                else if (square[1][0] == 5)
                        md += 3;
                else if (square[1][0] == 6)
                        md += 2;
                else if (square[1][0] == 7)
                        md += 1;
                else if (square[1][0] == 8)
                        md += 0;
                if (square[1][1] == 1)
                        md += 2;
                else if (square[1][1] == 2)
                        md += 1;
                else if (square[1][1] == 3)
                        md += 2;
                else if (square[1][1] == 4)
                        md += 1;
                else if (square[1][1] == 5)
                        md += 2;
                else if (square[1][1] == 6)
                        md += 1;
                else if (square[1][1] == 7)
                        md += 2;
                else if (square[1][1] == 8)
                        md += 1;
                if (square[1][2] == 1)
                        md += 3;
                else if (square[1][2] == 2)
                        md += 2;
                else if (square[1][2] == 3)
                        md += 1;
                else if (square[1][2] == 4)
                        md += 0;
                else if (square[1][2] == 5)
                        md += 1;
                else if (square[1][2] == 6)
                        md += 2;
                else if (square[1][2] == 7)
                        md += 3;
                else if (square[1][2] == 8)
                        md += 2;
                if (square[2][0] == 1)
                        md += 2;
                else if (square[2][0] == 2)
                        md += 3;
                else if (square[2][0] == 3)
                        md += 4;
                else if (square[2][0] == 4)
                        md += 3;
                else if (square[2][0] == 5)
                        md += 2;
                else if (square[2][0] == 6)
                        md += 1;
                else if (square[2][0] == 7)
                        md += 0;
                else if (square[2][0] == 8)
                        md += 1;
                if (square[2][1] == 1)
                        md += 3;
                else if (square[2][1] == 2)
                        md += 2;
                else if (square[2][1] == 3)
                        md += 3;
                else if (square[2][1] == 4)
                        md += 2;
                else if (square[2][1] == 5)
                        md += 1;
                else if (square[2][1] == 6)
                        md += 0;
                else if (square[2][1] == 7)
                        md += 1;
                else if (square[2][1] == 8)
                        md += 2;
                if (square[2][2] == 1)
                        md += 4;
                else if (square[2][2] == 2)
                        md += 3;
                else if (square[2][2] == 3)
                        md += 2;
                else if (square[2][2] == 4)
                        md += 1;
                else if (square[2][2] == 5)
                        md += 0;
                else if (square[2][2] == 6)
                        md += 1;
                else if (square[2][2] == 7)
                        md += 2;
                else if (square[2][2] == 8)
                        md += 3;
                return md;
        }

        boolean solve(char[][] solution) {
                boolean found;
                int fCost, i, j, k, m = 0;
               
                fCost = DFSContour(solution, Infinity, 0, board);
                if (flag == 1)
                        return true;
                else if (fCost == Infinity)
                        return false;
                return false;
        }

        int getMoves() {
                return moves;
        }
}

class Puzzle8I implements Runnable {
        char[][] solution = null;
        int moves;
        PuzzleI puzzleI = null;

        public Puzzle8I () {
                solution = new char[PuzzleI.MaxMoves][9];
                do
                        puzzleI = new PuzzleI();
                while (!puzzleI.solve(solution));
        }

        public void run() {
                Puzzle8IFrame puzzle8IFrame = new Puzzle8IFrame(solution[0]);
               
                moves = puzzleI.getMoves() - 1;
                System.out.println("moves = " + moves);
                for (int i = 1; i < moves + 1; i++) {
                        while (!puzzle8IFrame.getNext())
                                Thread.yield();
                        puzzle8IFrame.setNext(false);
                        puzzle8IFrame.draw(solution[i]);
                }
        }

        static void main(String[] arg) {
                (new Puzzle8I()).run();
        }
}


green_Dream ۰۶-۶-۱۳۸۹ ۰۳:۱۰ بعد از ظهر

با سلام و احترام

ابتدا از مدير كل سايت بسيار ممنون و سپاسگزارم كه لطف مي كنند و به ديدگاهها و تاپيك هاي دوستان توجه مي كنند !!!!!!
ميشه خواهش كنم اگر درباره معماي هشت پازل به روش greedy search (جستجوي حريصانه) نيز ،سورس كدي داشتيد در فروم قرار دهيد

با تشكر فراوان

Astaraki ۰۶-۷-۱۳۸۹ ۱۰:۴۳ قبل از ظهر

نقل قول:

نوشته اصلي بوسيله green_dream (پست 8696)
با سلام و احترام

ابتدا از مدير كل سايت بسيار ممنون و سپاسگزارم كه لطف مي كنند و به ديدگاهها و تاپيك هاي دوستان توجه مي كنند !!!!!!
ميشه خواهش كنم اگر درباره معماي هشت پازل به روش greedy search (جستجوي حريصانه) نيز ،سورس كدي داشتيد در فروم قرار دهيد

با تشكر فراوان

متأسفانه با اين روش چيزي پيدا نکردم!

البته هميشه مدير نبايد پاسخگو باشه:2:انجمن راه انداختيم تا همه تو حل مشکلات همديگه کمک کنن نه اينکه فقط درخواست کنن:29: البته شما فعاليت داريد:25: ولي کلاً از بقيه دوستان هم ميخوام که همون اندازه که از اينجا استفاده ميکنن، همون اندازه هم خرج کنن!

samira777 ۰۷-۲۳-۱۳۸۹ ۱۱:۴۱ بعد از ظهر

سلام
معماي 8 رو با الگوريتم اجتماع ذرات pso هم ميشه حل كرد؟
اگه آره، كدي توو متلب يا ++c مي خواستم.
ممنون

batking ۰۸-۲-۱۳۸۹ ۰۳:۴۱ بعد از ظهر

سلام دوستان

استاد ما گفته بود که حالتهای اولیه برای این مساله !9 حالت هستش.
که نصف این حالتها به جواب میرسه و نصف دیگشون به جواب نمیرسن.

کسی نظری داره؟

Raji ۰۸-۲۲-۱۳۸۹ ۰۳:۴۱ بعد از ظهر

#moamaye 8 be zabane c

Astaraki ۰۸-۲۲-۱۳۸۹ ۰۶:۵۵ بعد از ظهر

پیاده سازی معماي 8 با#C و به کمک روش جستجوی A-star

bijibuji ۰۹-۱۳-۱۳۸۹ ۰۸:۵۰ بعد از ظهر

حل معمای پازل 8 با کد سی پلاس پلاس
 
خدمت لیلا خانوم که دنبالش می گشتن

تابع مکاشفه ای (هیورستیک) ای که به کار رفته فاصله منهتن هستش.
این هم منبع

كد:

class Piece
{
    public int X;
    public int Y;
    public readonly int Number;

    int TargetX{get{return (Number-1)%3;}}
    int TargetY{get{return (Number-1)/3;}}

    int CalculateDistanceFromGoal()
    {
        int dx=X-TargetX;
        int dy=Y-TargetY;
        return Math.Abs(dx)+Math.Abs(dy);
    }

    public Piece(int number,int x,int y)
    {
        Number=number;
        X=x;
        Y=y;
    }
}


}

int Heuristic(Piece[] pieces)
{
    int result=0;
    foreach(Piece piece in pieces)
    {
        result+=piece.CalculateDistanceFromGoal();
    }
    return result;
}


profnami ۰۹-۲۴-۱۳۸۹ ۰۹:۳۵ بعد از ظهر

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

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

من الان همه ی تاپیک ها رو خوندم . آخرش نفهمیدم که شما چی میخواید انجام بدید

bijibuji ۰۹-۲۶-۱۳۸۹ ۰۳:۲۴ قبل از ظهر

نقل قول:

نوشته اصلي بوسيله profnami (پست 13771)
بهتر نیست که اول مساله و راه حل هاش رو تعریف کنید . بعد سورس بزارید ؟

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

من الان همه ی تاپیک ها رو خوندم . آخرش نفهمیدم که شما چی میخواید انجام بدید

من متوجه پیشنهاد شما نشدم
یه دوستی سوالی پرسیده بود و من هم جوابش رو دادم.
سوال شما چیه؟ اگر سوالی دارید بپرسید
اگر جوابی دارید به پرسش دوستتون ، ذکر کنید
در غیر اینصورت من نمی فهمم که شما منظورتون چیه ؟

profnami ۰۹-۲۷-۱۳۸۹ ۰۱:۵۵ قبل از ظهر

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

masood ۱۰-۲۴-۱۳۸۹ ۰۶:۲۶ بعد از ظهر

تعریف معمای هشت
 
نقل قول:

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

شرح معمای 8 اینه که فرض می کنیم یک جدول 3 در 3 داریم که اعداد 1 تا 8 رو بدون تکرار توش نوشتن و یک خونه هم خالی مونده که قصه سر همون خونه خالیه. شما می تونی هرکدوم از اعداد رو که همسایه خونه خالی باشه بکشی پایین بالا چپ یا راست تا توو خونه خالی جا بگیره و البته جای خودش خالی بشه.
لذا نتیجه می گیریم همیشه یه خونه خالیه.
اگر فرض کنیم اعداد بصورت تصادفی توی این خونه ها قرار گرفته باشند هدف از این الگوریتم ها اینه که با جابجا کردن خونه خالی بتونن به یه حالتی برسن که اول خونه خالی باشه بعد 1 و بعد 2 و بعد در سطر بعدی 3 و الی آخر. یعنی جدول مذکور رو باید مرتب کنی
همین:23:

*shabnam* ۱۲-۲۸-۱۳۸۹ ۱۲:۰۳ قبل از ظهر

از دوستای محترمی که این تاپیک رو دیدن، کسی هست که سورسc++ این بازی رو که دوستان لطف کردن و گذاشتن رو اجرا کرده باشه؟
من که اجراش میکنم error میده

zohresh ۱۲-۲۸-۱۳۸۹ ۰۸:۳۵ قبل از ظهر

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

batking ۱۲-۲۹-۱۳۸۹ ۰۱:۵۲ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله *shabnam* (پست 16389)
از دوستای محترمی که این تاپیک رو دیدن، کسی هست که سورسc++ این بازی رو که دوستان لطف کردن و گذاشتن رو اجرا کرده باشه؟
من که اجراش میکنم error میده

من به زبان دلفی دارمش

shadi67 ۰۱-۱۵-۱۳۹۰ ۰۹:۱۲ بعد از ظهر

سلام اگه امکان داره حل این برنامه رو با الگوریتم رقابت استعماری بذارید؟

mohammad.eshkiti ۰۱-۲۱-۱۳۹۰ ۰۷:۱۶ قبل از ظهر

puzzel 8
 
ba salam b dustaye azizam,,mikhastam khahesh konam darbare puzzel 8 ravesh haye mokhtalete algoritmesh moarefi va rahnami konid.ba tashakor

maryam20 ۰۱-۲۳-۱۳۹۰ ۱۱:۲۳ قبل از ظهر

8puzzle
 
salam.man halle 8puzzle be ravesh A* be zabane c++ mikham mamnoon misham age kesi dashte bashe

mz123 ۰۲-۷-۱۳۹۰ ۰۲:۱۵ بعد از ظهر

9puzzle
 
سلام دوستان
کسی هست که کد جاوای 9 پازل رو با روش ida* داشته باشه ؟
(9 پازل همون بازی 8پازلی است که خانه ی خالی ندارد و اعداد 1 تا 9 را شامل می شود)
تابع هیوریستیک اونو چه تابعی باید بگیرم؟
ممنون می شم اگه زودتر کسی جوابم رو بده

soodeh1010 ۰۲-۱۷-۱۳۹۰ ۰۵:۳۰ قبل از ظهر

سلام . عزیز چیزی که میخوای توی همین تاپیک هست اما بدون توضیح هست و من که کامپایل کردم error میده....

soodeh1010 ۰۲-۱۹-۱۳۹۰ ۰۵:۳۱ قبل از ظهر

سلام . لطفا بگین برنامه هایی که گذاشتین تو چه ورژنی اجرا میشه؟


كد:

#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++[/QUOTE]

asal_12 ۰۲-۲۰-۱۳۹۰ ۰۹:۱۹ قبل از ظهر

سلام دوستان خوبید؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟ ؟میشه برای من برنامه هشت پازل به روشa* به زبان ++cایمیل کنییییییییییییییید
خواهش میکنم دوستان

sahel_6432 ۰۲-۲۰-۱۳۹۰ ۰۶:۱۰ بعد از ظهر

سلام خدمت همه دوستان.من هم تازه واردم و هم چیزی از هوش مصنوعی نمیدونم.این ترم جزو واحدهای درسیمه.استادمون خواسته معمای 8 رو به روش دستی روی کاغذ براش حل کنیم و به بهترین جواب برسیم.آیا راهی یا فرمولی هست که از همون اول تشخیص بدیم روش درست چیه؟
ممنون از همه.:53:

yekta kh ۰۲-۲۲-۱۳۹۰ ۱۰:۲۲ قبل از ظهر

برنامه حل معمای پازل 8 را به روش *aمیخواستم خواهش میکنم اگه دارید تا حداکثر27 اردیبهشت به این آدرس ایمیل کنید khodadadi.elham@yahoo.com

hamidreza_kh ۰۲-۲۴-۱۳۹۰ ۰۳:۳۱ بعد از ظهر

كد:


//h_r_k_s@yahoo.com
//IDS code
#include <conio.h>
#include <iostream.h>

int g[10]={0,1,2,3,4,5,6,7,8,0};//goal
int s[10]={0,3,2,4,5,6,7,8,0,1};//initial state


void IDS(int,int,int);
void init(int [][5],int,int);
void succesor(int ,int );
int goalcheck();
int d=0;
int flag=0;
int arr[2][100];
int r=0;
int t;
void main()
{
        clrscr();
        int l=1;
        while(d==0)
        {
                IDS(1,1,l);
                if(flag==1)
                {
                        d=1;
                }
                l++;
        }
        l--;
        cout<<l;
        for(int i=0;i<t;i++)
        {
                cout<<"\n"<<arr[0][i]<<" "<<arr[1][i];
        }
        getch();
}
void IDS(int i,int j,int l)
{
        if(goalcheck()==1)
        {

                l=0;
                flag=1;
                t=r;
                return;
        }
        else if(l>0)
        {
                int sucarray[2][5];
                init(sucarray,j,i);
                int k=0;
                while(sucarray[0][k]!=-1 && flag!=1)
                {
                        succesor(sucarray[0][k],sucarray[1][k]);
                        arr[0][r]=sucarray[0][k];
                        arr[1][r]=sucarray[1][k];
                        r++;
                        IDS(sucarray[0][k],sucarray[1][k],l-1);
                        succesor(sucarray[0][k],sucarray[1][k]);
                        k++;
                        r--;
                }
                return;
        }
}
void init(int sucarray[][5],int a,int b)
{
        int i=1;
        while(s[i]!=0)
                i++;
        if(i==1)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i+1;//1:2
                sucarray[0][1]=i;
                sucarray[1][1]=i+3;//1:4
                sucarray[0][2]=-1;
        }else if(i==2)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i-1;//2:1
                sucarray[0][1]=i;
                sucarray[1][1]=i+1;//2:3
                sucarray[0][2]=i;
                sucarray[1][2]=i+3;//2:5
                sucarray[0][3]=-1;
        }else if(i==3)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i-1;//3:2
                sucarray[0][1]=i;
                sucarray[1][1]=i+3;//3:6
                sucarray[0][2]=-1;
        }else if(i==4)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i+1;//4:5
                sucarray[0][1]=i;
                sucarray[1][1]=i+3;//4:7
                sucarray[0][2]=i;
                sucarray[1][2]=i-3;//4:1
                sucarray[0][3]=-1;
        }else if(i==5)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i+1;//5:6
                sucarray[0][1]=i;
                sucarray[1][1]=i-1;//5:4
                sucarray[0][2]=i;
                sucarray[1][2]=i-3;//5:2
                sucarray[0][3]=i;
                sucarray[1][3]=i+3;//5:8
                sucarray[0][4]=-1;
        }else if(i==6)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i-3;//6:3
                sucarray[0][1]=i;
                sucarray[1][1]=i-1;//6:5
                sucarray[0][2]=i;
                sucarray[1][2]=i+3;//6:9
                sucarray[0][3]=-1;
        }else if(i==7)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i+1;//7:8
                sucarray[0][1]=i;
                sucarray[1][1]=i-3;//7:4
                sucarray[0][2]=-1;
        }else if(i==8)
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i-1;//8:7
                sucarray[0][1]=i;
                sucarray[1][1]=i+1;//8:9
                sucarray[0][2]=i;
                sucarray[1][2]=i-3;//8:5
                sucarray[0][3]=-1;
        }else
        {
                sucarray[0][0]=i;
                sucarray[1][0]=i-1;//9:8
                sucarray[0][1]=i;
                sucarray[1][1]=i-3;//9:6
                sucarray[0][2]=-1;
        }
        int k=0;
        while(sucarray[0][k]!=-1)
        {
                if(sucarray[1][k]==b)
                {
                        for(int v=k;v<4;v++)
                        {
                                sucarray[0][v]=sucarray[0][v+1];
                                sucarray[1][v]=sucarray[1][v+1];
                        }
                }
                k++;
        }
}
void succesor(int a,int b)
{
        int temp;
        temp=s[a];
        s[a]=s[b];
        s[b]=temp;
}
int goalcheck()
{
        for(int i=1;i<=9;i++)
        {
                if(s[i]!=g[i])
                        return -1;
        }
        return 1;
}



زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۱۱:۵۸ قبل از ظهر ميباشد.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.