[Mohsen Omidvar]

[font=tahoma, geneva, sans-serif]معمای 8  یا  پازل 8-puzzle[/font]

[font=tahoma, geneva, sans-serif]دوستانی که در  رشته های کامپیوتر، فناوری اطلاعات و هوش مصنوعی تحصیل می کنند حتما با بازی پازل 8 آشنایی  دارند. این بازی  تقریبا پای ثابت اکثر معماها در آموزش ابتدایی  هوش مصنوعی است.[/font]
[font=tahoma, geneva, sans-serif]این معما از یک جدول 3 در 3 تشکیل شده است که می شود 9 خانه.[/font]
[font=tahoma, geneva, sans-serif]حالا در این جدول اعداد یک تا هشت قرار می گیرند و همچنین یکی از خانه ها خالی است.این معما شامل حالت اولیه و حالت نهایی است که باید به آن برسیم.[/font]
[font=tahoma, geneva, sans-serif]حالت اولیه :[/font]
[font=tahoma, geneva, sans-serif]در این حالت اعداد می توانند به هر ترتیبی در جدول قرار گیرند.[/font]
[font=tahoma, geneva, sans-serif]حالت نهایی :[/font]
[font=tahoma, geneva, sans-serif]حالتی است که از ما می خواهند به آن برسیم و این کار با حرکت خانه خالی میسر می شود. و باید از طریق قوانین زیر به آن رسید:[/font]
[font=tahoma, geneva, sans-serif]1- اگر سمت چپ خانه خالي ، عدد باشد حرکت خانه خالي به سمت چپ[/font]
[font=tahoma, geneva, sans-serif]2- اگر سمت راست خانه خالي ، عدد باشد حرکت خانه خالي به سمت راست[/font]
[font=tahoma, geneva, sans-serif]3- اگر سمت بالا خانه خالي ، عدد باشد حرکت خانه خالي به سمت بالا[/font]
[font=tahoma, geneva, sans-serif]4- اگر سمت پايين خانه خالي ، عدد باشد حرکت خانه خالي به سمت پايين[/font]
 
[font=tahoma, geneva, sans-serif]الگوریتم های متعددی برای این کار وجود دارد که یکی از آنها الگوریتم ژنتیک است.که در واقع این برنامه توسط این الگوریتم هوش مصنوعی و زبان برنامه نویسی سی شارپ پیاده سازی شده است.[/font]
 

کد:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
namespace _8
{
   public partial class Form1 : Form
   {
       public Form1()
       {
           InitializeComponent();
       }
       int[,] first = new int[3, 3];
       int[,] final = new int[3, 3];
       int[, ,] temp = new int[3, 3, 10000];
       string[] tempstaus = new string[10000];
       int[,] realtemp = new int[3, 3];
       int[,] qu = new int[3, 10000];

       private void showtemp(int qun)        
       {
           string s = "";
           listBox2.Items.Clear();
           for (int i = 0; i <= qun; i++)
           {
               for (int j = 0; j < 3; j++)
               {
                   for (int k = 0; k < 3; k++)
                   {                        
                       s += temp[j, k, i].ToString() + "  ";                        
                   }
                   listBox2.Items.Add(s);
                   s = "";
               }
               listBox2.Items.Add(tempstaus[i]);
               listBox2.Items.Add("=====================");    
               
           }

       
       }
       private void insertff()
       {
           first[0, 0] = Convert.ToInt32(textBox1.Text);
           first[0, 1] = Convert.ToInt32(textBox2.Text);
           first[0, 2] = Convert.ToInt32(textBox3.Text);
           first[1, 0] = Convert.ToInt32(textBox4.Text);
           first[1, 1] = Convert.ToInt32(textBox5.Text);
           first[1, 2] = Convert.ToInt32(textBox6.Text);
           first[2, 0] = Convert.ToInt32(textBox7.Text);
           first[2, 1] = Convert.ToInt32(textBox8.Text);
           first[2, 2] = Convert.ToInt32(textBox9.Text);
           final[0, 0] = Convert.ToInt32(textBox18.Text);
           final[0, 1] = Convert.ToInt32(textBox17.Text);
           final[0, 2] = Convert.ToInt32(textBox16.Text);
           final[1, 0] = Convert.ToInt32(textBox15.Text);
           final[1, 1] = Convert.ToInt32(textBox14.Text);
           final[1, 2] = Convert.ToInt32(textBox13.Text);
           final[2, 0] = Convert.ToInt32(textBox12.Text);
           final[2, 1] = Convert.ToInt32(textBox11.Text);
           final[2, 2] = Convert.ToInt32(textBox10.Text);
       }
       private int h1(int n)
       {
           int h = 0;
           for (int i = 0; i < 3; i++)
               for (int j = 0; j < 3; j++)
                   if (temp[i, j, n] != final[i, j])
                   {
                       if(temp[i, j, n] !=0)
                       h++;
                   }
           int x=0;
           foreach(char  s in tempstaus[n])
                if (s == '/')
                   x++;

   
               return h+x ;
       }
       private void run()
       {
           #region first node
           for (int i = 0; i < 3; i++)
               for (int j = 0; j < 3; j++)
                   temp[i, j, 0] = first[i, j];
           tempstaus[0] = "0";
           int qun = 0;
           qu[0, qun] = qun ;
           qu[1, qun] = h1(qun);
           qu[2, qun] = 0;
           listBox1.Items.Add(qu[0, qun].ToString() + "         h1= " + qu[1, qun].ToString() + "       " + tempstaus[qun]);
           Application.DoEvents();
#endregion
           while (true)
           {
                   int min=0;
                   int minmain = 0;
               for (int i = 0; i <= qun ; i++)// peyda kardane avvalin onsore peymude nashode
               {
                   if(qu[2,i]==0)
                   {
                       min = qu[1, i];
                       minmain = i;
                       break;
                   }
               }
            for (int i = 0; i <= qun; i++)// peyda kardane kuchiktarin onsor
               {
                   if (qu[1, i] < min && qu[2, i]==0)
                   {
                       min = qu[1, i];
                       minmain = i;
                   }
               }
              // MessageBox.Show("min= " + min.ToString() + "  minmain =  " + minmain.ToString() + "  qun=" + qun.ToString());

               int r=0, c=0;
               for (int i = 0; i < 3; i++)//peyda kardane khune khali
                   for (int j = 0; j < 3; j++)
                       if (temp[i, j, minmain] == 0)
                       {
                           r = i;
                           c = j;
                           break;                      
                       }
               for (int i = 0; i < 3; i++) // enteghal tempe morede nazar be tempreal
                   for (int j = 0; j < 3; j++)
                       realtemp[i, j] = temp[i, j, minmain];
             // MessageBox.Show(minmain.ToString());
               qu[2, minmain] = 1;
               /////////////////////////////////////////////tolide farzandan////////////////////////////////////////////////
               showtemp(qun);
               int x = 0;
               foreach (char s in tempstaus[minmain ])
                   if (s == '/')
                       x++;
               if (h1(minmain)-x  == 0)
               {
                   MessageBox.Show("found !!!     masir  = "+tempstaus[minmain].ToString());
                   break;
               }
               #region  tolide farzand
               //===================================check resltemp != jadd===================================

               //-----------------l
               if (c > 0)
               {
                   qun++;
                   realtemp[r, c] = realtemp[r, c - 1];
                   realtemp[r, c - 1]=0;
                   tempstaus[qun] =tempstaus[minmain]+ "/left";
                   for (int i = 0; i < 3; i++)
                       for (int j = 0; j < 3; j++)
                           temp[i, j, qun] = realtemp[i, j];
                   qu[0, qun] = qun;
                   qu[1, qun] = h1(qun);
                   qu[2, qun] = 0;
                   listBox1.Items.Add(qu[0, qun].ToString() + "         h1= " + qu[1, qun].ToString() + "       " + tempstaus[qun]);
                   Application.DoEvents();
               }
               //-----------------r
               if (c < 2)
               {
                   for (int i = 0; i < 3; i++) // enteghal tempe morede nazar be tempreal
                       for (int j = 0; j < 3; j++)
                           realtemp[i, j] = temp[i, j, minmain];
                   qun++;
                   realtemp[r, c] = realtemp[r, c+1];
                   realtemp[r, c+ 1] = 0;
                   for (int i = 0; i < 3; i++)
                       for (int j = 0; j < 3; j++)
                           temp[i, j, qun] = realtemp[i, j];
                   tempstaus[qun] = tempstaus[minmain] + "/right";
                   qu[0, qun] = qun;
                   qu[1, qun] = h1(qun);
                   qu[2, qun] = 0;
                   listBox1.Items.Add(qu[0, qun].ToString() + "         h1= " + qu[1, qun].ToString() + "       " + tempstaus[qun]);
                   Application.DoEvents();
               }
               //-----------------up
               if (r>0)
               {
                   for (int i = 0; i < 3; i++) // enteghal tempe morede nazar be tempreal
                       for (int j = 0; j < 3; j++)
                           realtemp[i, j] = temp[i, j, minmain];
                   qun++;
                   realtemp[r, c] = realtemp[r-1, c ];
                   realtemp[r-1, c ] = 0;
                   for (int i = 0; i < 3; i++)
                       for (int j = 0; j < 3; j++)
                           temp[i, j, qun] = realtemp[i, j];
                   tempstaus[qun] = tempstaus[minmain] + "/up";
                   qu[0, qun] = qun;
                   qu[1, qun] = h1(qun);
                   qu[2, qun] = 0;
                   listBox1.Items.Add(qu[0, qun].ToString() + "         h1= " + qu[1, qun].ToString() + "       " + tempstaus[qun]);
                   Application.DoEvents();
               }
               //-----------------down
               if (r < 2)
               {
                   for (int i = 0; i < 3; i++) // enteghal tempe morede nazar be tempreal
                       for (int j = 0; j < 3; j++)
                           realtemp[i, j] = temp[i, j, minmain];
                   qun++;
                   realtemp[r, c] = realtemp[r + 1, c];
                   realtemp[r + 1, c] = 0;
                   for (int i = 0; i < 3; i++)
                       for (int j = 0; j < 3; j++)
                           temp[i, j, qun] = realtemp[i, j];
                   tempstaus[qun] = tempstaus[minmain] + "/down";
                   qu[0, qun] = qun;
                   qu[1, qun] = h1(qun);
                   qu[2, qun] = 0;
                   listBox1.Items.Add(qu[0, qun].ToString() + "         h1= " + qu[1, qun].ToString() + "       " + tempstaus[qun]);
                   Application.DoEvents();
               }
#endregion
           }
       }
       private void button1_Click(object sender, EventArgs e)
       {
           listBox1.Items.Clear();
           listBox2.Items.Clear();
           insertff();
           run();
       }
       private void button2_Click(object sender, EventArgs e)
       {
           System.Diagnostics.Process.Start("http://www.sourcecodes.ir");
       }

   }
}