八数码难题
Time Limit:1000MS Memory Limit:65536K
Total Submit:0 Accepted:0
Description
在3×3的棋盘上，有8个数，分别是1,2,3,4,5,6,7,8 和一个空格(0)，如图
2 8 3
1 6 4
7 0 5
假设给定目标状态
1 2 3
8 0 4
7 6 5
问，给定状态至少经过几次变换才能到达目标状态。每次变换是指把空格上下左右其中的一个数移到空格处。
Input
两个3×3的矩阵，0表示空格，第一个表示初始状态，第二个表示目标状态
Output
最少步数，如果无解就输出-1
Sample Input
2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5
Sample Output
5
Hint
队列广搜 经典题目
Source
追问：。。。。。大哥。。我那道八数码题的得数你的程序能出来吗？答案：解题步骤：1、 问题表示：
问题表示的核心是如何存储搜索过程中得到的状态。本人是这样存储的：对每个状态用一个9位数存储，例如：
把初始状态：
8 0 3
2 1 4
7 6 5
存储为一个9为数：803214765
2、 解题算法：
本人用了广度优先搜索这种策略进行搜索，且其搜索深度限制在1000内，其代码实现如下：
using System;
using System.Collections.Generic;
using System.Text;
using System.Windows.Forms;
namespace 八数码难题
{
class MagicFind //MagicFind这个类是用广度优先搜索方法找到八数码问题的最佳解
{
public System.Collections.ArrayList arraylist;
public int[] a;//用于存储临时状态
public int v;//记录初始状态的值
static int[,] dir;//状态转移的4个方向
int time;//限定搜索深度
int max;
const int V = 123804765; //目的状态
public MagicFind() {
arraylist = new System.Collections.ArrayList();
a = new int[9];
a = new int[9] { 2,8,3,1,0,4,7,6,5};
v = 283104765;
dir = new int[4, 2] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
}
public bool find() //广度优先搜索
{
System.Collections.ArrayList p, q;//p是搜索状态记录,q是搜索路径记录
int j = 0, k = 1; p = new System.Collections.ArrayList(); q = new System.Collections.ArrayList();
p.Clear(); q.Clear();
p.Add(v); q.Add(-1);
while (j < k)
{
int zero = toArray((int)p[j]);
int i;
for (i = 0; i < 4; i++)
{
int x = zero / 3; int y = zero % 3;
if (x + dir[i,0] < 0 || x + dir[i,0] > 2 || y + dir[i,1] < 0 || y + dir[i,1] > 2) continue;
x = x + dir[i,0]; y = y + dir[i,1];
exchange(zero, x * 3 + y);
int sum = toValue(a);
int r;
exchange(zero, x * 3 + y);
for (r = 0; r < k; r++) if ((int)p[r] == sum) break;
if (r < k) continue;
p.Add(sum); q.Add(j);
if (sum == V) { break; }
k++;
}
if (i < 4 || j == 1000) break;
j++;
}
if (j < k && j < 1000)
{
while ((int)q[k] != -1)
{
arraylist.Add(p[k]);
k = (int)q[k];
}
return true;
}
return false;
}
int toValue(int[] a) //把数组a变成一个9位的数值
{
int sum = 0;
for (int i = 0; i < 9; i++) sum = sum * 10 + a[i];
return sum;
}
int toArray(int value) //把数值value转换成一个数值a[9]
{
int zero = -1;
for (int i = 8; i >= 0; i--)
{
a[i] = value % 10;
value /= 10;
if (a[i] == 0) zero = i;
}
return zero;
}
void exchange(int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
};
}
3、 效果图：
图1 初始界面
图2 自动演示
图3 游戏结束
4、 软件功能介绍：
本软件分两大功能：用户完成游戏和游戏自动演示。还提供了对游戏初始状态进行随机生成的功能，而且随机生成的初始状态满足在1000步内有解。软件界面上的”开始游戏”按钮表示用户进入游戏，这时用户便可移动数字方块(只需单击你所要移动的数字方块，它便会移到空位)；”随机初始化”按钮完成对游戏初始状态的随机生成；”自动演示”按钮完成游戏的自动演示功能
