[Mohsen Omidvar]

معمای 8  یا  پازل 8-puzzle

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

کد:

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");
       }

   }
}