#c#用广度优先搜索求八数码最优解
#搜索遍历失败
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace 拼图游戏1._0._4
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
public static int[][] map = new int[3][] { new int[3] { 0, 1, 2 }, new int[3] { 3, 4, 5 }, new int[3] { 6, 7, 8 } };//正确的地图
public static int[][] arr = new int[3][];//储存随机地图
public static int[] a = new int[9] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
public static int min = 99999;
public static int x, y;
public static int[][] Newsorting(int []a)//随机打乱
{
Random r = new Random();
for (int i = 0; i < a.Length; i++)
{
int temp = a[i];
int randomindex = r.Next(0, a.Length);
a[i] = a[randomindex];
a[randomindex] = temp;
}
int[][] arr= new int[][] { new int[] { a[0], a[1] ,a[2]},new int[] { a[3], a[4], a[5] },new int[] { a[6], a[7], a[8] } };
return arr;
}
public static void bfs()//广度优先搜素
{
HuaRongDao hua = new HuaRongDao();
int step=0, tx, ty,startx,starty;
bool flag = false;
ArrayList set = new ArrayList();//记录走过的路径
Queue q = new Queue();
int[][] next = new int[][]
{
new int[] { 0, 1 }, //向右
new int[] { 1, 0 }, //向下
new int[] { 0, -1 },//向左
new int[] { -1, 0 } //向上
};
q.Enqueue(arr);
//将初始地图加入到队列
set.Add(arr);//记录初始地图
while (q.Count>0) //当队列不为空时循环
{
hua.Startdirection(arr);//获取当前0的位置
startx = x;
starty = y;
for (int i = 0; i < next.Length; i++)
{
//计算下一步的坐标
tx = startx + next[i][0];
ty = starty + next[i][1];
//判断是否越界
if (tx < 0 || tx > 2 || ty < 0 || ty > 2)
{
continue;
}
else
{
arr = hua.Move(startx, starty, tx, ty);//交换位置
bool s = set.Contains(arr);//判断是否有重复
if (s == false)
{
set.Add(arr);//将交换后的地图保存
q.Enqueue(arr);
//把新的地图加到队列中
hua.Startdirection(arr);//更新0的坐标
startx = x;
starty = y;
}
}
}
flag = over(arr, map);//判断是否完成
if (flag == true)//如果找到终点，停止扩展，任务结束，退出while循环
{
break;
}
object used = q.Dequeue();
step++;
if (step < min) { min = step; }
}
}
public static bool over(int[][]arr,int[][]map)
{ for(int i=0;i<3;i++)
{ for (int j = 0; j < 3; j++) { if (arr[i][j] == map[i][j])
return true;
} }
return false; }
class HuaRongDao
{
public int Startdirection(int[][] arr)//找到地图中0的初始横纵坐标
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < arr[i].Length; j++)
{
if (arr[i][j] == 0)
{
x = i;
y = j;
}
}
}
return x&y;
}
public int[][] Move(int x,int y,int tx,int ty)
{
int temp;
temp = arr[tx][ty];
arr[tx][ty] = 0;
arr[x][y] = temp;
return arr;
}
}
private void button1_Click(object sender, EventArgs e)
{
arr = Newsorting(a);
label1.Text = Convert.ToString(arr[0][0]);
label2.Text = Convert.ToString(arr[0][1]);
label3.Text = Convert.ToString(arr[0][2]);
label4.Text = Convert.ToString(arr[1][0]);
label5.Text = Convert.ToString(arr[1][1]);
label6.Text = Convert.ToString(arr[1][2]);
label7.Text = Convert.ToString(arr[2][0]);
label8.Text = Convert.ToString(arr[2][1]);
label9.Text = Convert.ToString(arr[2][2]);
}
private void button2_Click(object sender, EventArgs e)
{
HuaRongDao hua = new HuaRongDao();
hua.Startdirection(arr);
bfs();
textBox1.Text = "最短路径：" + Convert.ToString(min);
}
}
}
