23-01-2015، 03:06 AM
معمای 8 یا پازل 8-puzzle
دوستانی که در رشته های کامپیوتر، فناوری اطلاعات و هوش مصنوعی تحصیل می کنند حتما با بازی پازل 8 آشنایی دارند. این بازی تقریبا پای ثابت اکثر معماها در آموزش ابتدایی هوش مصنوعی است.
این معما از یک جدول 3 در 3 تشکیل شده است که می شود 9 خانه.
حالا در این جدول اعداد یک تا هشت قرار می گیرند و همچنین یکی از خانه ها خالی است.این معما شامل حالت اولیه و حالت نهایی است که باید به آن برسیم.
حالت اولیه :
در این حالت اعداد می توانند به هر ترتیبی در جدول قرار گیرند.
حالت نهایی :
حالتی است که از ما می خواهند به آن برسیم و این کار با حرکت خانه خالی میسر می شود. و باید از طریق قوانین زیر به آن رسید:
1- اگر سمت چپ خانه خالي ، عدد باشد حرکت خانه خالي به سمت چپ
2- اگر سمت راست خانه خالي ، عدد باشد حرکت خانه خالي به سمت راست
3- اگر سمت بالا خانه خالي ، عدد باشد حرکت خانه خالي به سمت بالا
4- اگر سمت پايين خانه خالي ، عدد باشد حرکت خانه خالي به سمت پايين
الگوریتم های متعددی برای این کار وجود دارد که یکی از آنها الگوریتم ژنتیک است.که در واقع این برنامه توسط این الگوریتم هوش مصنوعی و زبان برنامه نویسی سی شارپ پیاده سازی شده است.
دوستانی که در رشته های کامپیوتر، فناوری اطلاعات و هوش مصنوعی تحصیل می کنند حتما با بازی پازل 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");
}
}
}
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.