八数码问题还是很简单的。
一：游戏
Form1视图添加tableLayoutPanel控件：tableLayoutPanel1
初始化：//生成随机数列
private List<int> RandomNumber()
{
List<int> array = new List<int>();
Random rand = new Random();
int x;
while (array.Count < 9)
{
x = rand.Next(9);
if (array.IndexOf(x) == -1)
array.Add(x);
}
return array;
}
//判断是否有解
private bool IsPass(List<int> a)
{
int sum = 0;
for (int i = 0; i < 9; i++)
{
int s = 0;
if (a[i] == 0)
continue;
for (int j = 0; j < i; j++)
{
if (a[j] == 0)
continue;
if (a[i] > a[j])
s++;
}
sum += s;
}
if (sum % 2 == 0)
return true;
else
return false;
}
private void Create()
{
LabelList.Clear();
DataList.Clear();
tableLayoutPanel1.Controls.Clear();
while (true)
{
if (IsPass(RandomNumber()))
{
DataList = RandomNumber();
break;
}
else
{
continue;
}
}
Font m_font = new Font("宋体", 20, FontStyle.Bold);
Label m_label;
for (int i = 0; i < 9; i++)
{
m_label = new Label();
m_label.AutoSize = false;
m_label.Font = m_font;
m_label.Size = new Size(40, 40);
m_label.TextAlign = ContentAlignment.MiddleCenter;
if (DataList[i] == 0)
{
m_label.Text = " ";
pi = i;
}
else
{
m_label.Text = DataList[i].ToString();
}
LabelList.Add(m_label);
tableLayoutPanel1.Controls.Add(m_label);
}
}
private bool MoveUp()
{
int i = pi + 3;
if (i >= 0 && i <= 8)
{
Sweap(i);
return true;
}
else
return false;
}
private bool MoveDown()
{
int i = pi - 3;
if (i >= 0 && i <= 8)
{
Sweap(i);
return true;
}
else
return false;
}
private bool MoveLeft()
{
int i = pi + 1;
if (i <= 8 && i%3!=0)
{
Sweap(i);
return true;
}
else
return false;
}
private bool MoveRight()
{
int i = pi -1; ;
if (i >= 0 &&i%3!=2)
{
Sweap(i);
return true;
}
else
return false;
}
private void Sweap(int i)
{
label1.Text = (++step).ToString();
int inttemp;
string strtemp;
inttemp = DataList[pi];
DataList[pi] = DataList[i];
DataList[i] = inttemp;
strtemp = LabelList[pi].Text;
LabelList[pi].Text = LabelList[i].Text;
LabelList[i].Text = strtemp;
pi = i;
if (CheckOver())
MessageBox.Show("恭喜过关");
}
private bool CheckOver()
{
int i = 1;
foreach (int l in DataList)
{
if (l != i++ % 9)
return false;
}
return true;
}
==================打完收工。
二：求最短路径
最短路径用int表示数据。
移动的算法有点麻烦。用树状图理解比较容易。
初始状态
|
初始状态可生成的N种状态
|
N=1时的N种状态 …… N=N时的N种状态
这样分析。就需要有一个哈希表，存放已经生成的状态。
一个队列，存放将要生成的状态。
while(i++<362880)
{
int newcode=出队元素。
for(int i=0;i<4;i++) //每一个编码最多可以生成四种状态 :上下左右
{
if(……) //判断是否可以上(i=0) 下(i=1) 左(i=2) 右(i=3)移动。并且移动后的编码不存在于哈希表中
else
…… //哈希表.add(newcode,i);
if(newcode = endcode) //也就是通常的132456780
return;
}
}
如果要输出路径
从哈希表中返回就可以了。 不过因为是逆向的，方向应该是正好相反。
这种算法，应该就是广度优先搜索了。
2010-05-17 15:52
