九宫格有关问题，求思路
九宫格问题，求思路！
题目说明：
给定一个九宫格，里面填有1-9这9个数。
每次可以将相邻的两个数交换。
问最少几次，可以得到一个三阶幻方（每行，每列，和两条对角线上的和都是15）
输入说明：
三行，每行3个数
输出说明：
一行，为最少的步数（如果输入的就是三阶幻方，则输出0；如果不能在有限步后得到三阶幻方，输出-1）
输入样例：
1 2 8
3 5 4
6 7 8
输出样例：
5
------解决方案--------------------
试验了一种方式，得到解答大约需要几秒钟：
用递归做深度搜索，限制最大深度为40级。因为只要30多级就能保证把每一个数字送到指定地方了，不必搜太多。
每当搜索到一个解答，则更新最大深度限制，保证后面的搜索不会有更多浪费。
若当前还需要继续深入搜索，则循环列出所有12种改变并进行测试。当改变发生后没有出现曾有过的重复状态，则递归搜索。
代码如下：
题目说明：
给定一个九宫格，里面填有1-9这9个数。
每次可以将相邻的两个数交换。
问最少几次，可以得到一个三阶幻方（每行，每列，和两条对角线上的和都是15）
输入说明：
三行，每行3个数
输出说明：
一行，为最少的步数（如果输入的就是三阶幻方，则输出0；如果不能在有限步后得到三阶幻方，输出-1）
输入样例：
1 2 8
3 5 4
6 7 8
输出样例：
5
------解决方案--------------------
试验了一种方式，得到解答大约需要几秒钟：
用递归做深度搜索，限制最大深度为40级。因为只要30多级就能保证把每一个数字送到指定地方了，不必搜太多。
每当搜索到一个解答，则更新最大深度限制，保证后面的搜索不会有更多浪费。
若当前还需要继续深入搜索，则循环列出所有12种改变并进行测试。当改变发生后没有出现曾有过的重复状态，则递归搜索。
代码如下：
- C/C++ code
#include <iostream>
#include "grid9.h"
using namespace std;
struct notes
{
int n[40];
int top;
}route; // 用于记录路径
Grid9 grid; // 九宫格
int minDepth=40; // 记录最少步骤的步数
void inputG9();
void findG9(int depth);
int existing(int feature);
void main()
{
route.top=0; // 清空记录
inputG9(); // 输入原始数据
cout<<endl<<"开始计算步骤："<<endl;
findG9(0); // 调用搜索程序
cout<<"最少需要"<<minDepth<<"步"<<endl; // 输出最小步骤数
system("pause");
}
void inputG9()
{
int in[9];
cout<<"请输入原始九宫数据："<<endl;
cout<<"第一行：";
cin>>in[0]>>in[1]>>in[2];
cout<<"第二行：";
cin>>in[3]>>in[4]>>in[5];
cout<<"第三行：";
cin>>in[6]>>in[7]>>in[8];
for (int i=0;i<9;i++)
grid.setGrid(i,in[i]);
}
void findG9(int depth)
{
int gd=grid.difference();
route.n[route.top++]=gd;
if (gd==0) // 得到一个解
{
minDepth=depth;
route.top--;
return;
}
if (depth==minDepth) // 已经到了最大深度，回溯
{
route.top--;
return;
}
for (int i=0;i<12;i++)
{
grid.swap(i); // 交换i位置数据
gd=grid.difference();
if (!existing(gd))
findG9(depth+1); // 递归查找
grid.swap(i); // 恢复i位置数据
}
route.top--;
}
int existing(int feature)
{
for (int i=route.top-1;i>=0;i--)
if (feature==route.n[i])
return 1;
return 0;
}
------解决方案--------------------
Grid9类的代码：
grid9.h
- C/C++ code
class Grid9
{
private:
int grid[9]; // 存储着九宫状态
public:
int readGrid(int x, int y); // 读出九宫中数值
int feature(); // 返回当前九宫状态的特征值
void setGrid(int feature); // 按特征值设置九宫
void setGrid(int index, int v); // 按索引设置九宫
int difference(); // 返回当前九宫状态距离完美九宫的差距，差距为0则意味着已经是完美九宫。
void swap(int position); // 交换指定位置上的数。
};
------解决方案--------------------
为了避免用户误以为死机，加一个进程显示在里面......有点破坏完美的感觉
- C/C++ code
void findG9(int depth)
{
route.n[route.top++]=grid.feature();
if (grid.difference()==0) // 得到一个解
{
if (depth<minDepth)
cout<<"最短步骤已经下降到"<<depth<<endl;
minDepth=depth;
route.top--;
return;
}
if (depth==minDepth) // 已经到了最大深度，回溯
{
route.top--;
return;
}
for (int i=0;i<12;i++)
{
grid.swap(i); // 交换i位置数据
if (!existing(grid.feature()))
findG9(depth+1); // 递归查找
grid.swap(i); // 恢复i位置数据
}
route.top--;
}
------解决方案--------------------
可以输出最短步骤的daima：
- C/C++ code
#include <iostream>
#include "grid9.h"
using namespace std;
struct notes
{
int n[40];
int top;
}route,minRoute; // 用于记录路径
Grid9 grid; // 九宫格
int minDepth; // 记录最少步骤的步数
void inputG9();
void findG9(int depth);
int existing(int feature);
void showRoute();
void main()
{
char ch;
while (1)
{
route.top=0; // 清空记录
minRoute.top=0;
minDepth=10; // 测试中没有发现超过8步的组合，如果能证明这一点，把这个数字改成10就能加速很多了
inputG9(); // 输入原始数据
cout<<endl<<"开始计算步骤："<<endl;
findG9(0); // 调用搜索程序
cout<<"最少需要"<<minDepth<<"步"<<endl;
showRoute(); // 输出最小步骤
cout<<"------end------"<<endl<<"还要继续吗？(Y/N)";
cin>>ch;
if (ch=='N'||ch=='n')
break;
}
}
void inputG9()
{
int in[9];
cout<<"请输入原始九宫数据："<<endl;
cout<<"第一行：";
cin>>in[0]>>in[1]>>in[2];
cout<<"第二行：";
cin>>in[3]>>in[4]>>in[5];
cout<<"第三行：";
cin>>in[6]>>in[7]>>in[8];
for (int i=0;i<9;i++)
grid.setGrid(i,in[i]);
}
void findG9(int depth)
{
route.n[route.top++]=grid.feature();
if (grid.difference()==0) // 得到一个解
{
if (depth<minDepth)
{
cout<<"最短步骤已经下降到"<<depth<<endl;
minDepth=depth;
minRoute=route;
}
route.top--;
return;
}
if (depth==minDepth) // 已经到了最大深度，回溯
{
route.top--;
return;
}
for (int i=0;i<12;i++)
{
grid.swap(i); // 交换i位置数据
if (!existing(grid.feature()))
findG9(depth+1); // 递归查找
grid.swap(i); // 恢复i位置数据
}
route.top--;
}
int existing(int feature)
{
for (int i=route.top-1;i>=0;i--)
if (feature==route.n[i])
return 1;
return 0;
}
void showRoute()
{
cout<<endl<<"具体路径如下"<<endl;
for (int i=0;i<minRoute.top;i++)
{
cout<<"步骤"<<i<<endl;
cout<<' '<<minRoute.n[i]/1000000<<endl;
cout<<' '<<minRoute.n[i]/1000%1000<<endl;
cout<<' '<<minRoute.n[i]%1000<<endl;
cout<<endl;
if ((i+1)%3==0&&i<minRoute.top-1)
system("pause");
}
}