九宫格问题，求思路！
题目说明：
给定一个九宫格，里面填有1-9这9个数。
每次可以将相邻的两个数交换。
问最少几次，可以得到一个三阶幻方（每行，每列，和两条对角线上的和都是15）
输入说明：
三行，每行3个数
输出说明：
一行，为最少的步数（如果输入的就是三阶幻方，则输出0；如果不能在有限步后得到三阶幻方，输出-1）
输入样例：
1 2 8
3 5 4
6 7 8
输出样例：
5
[解决办法]
试验了一种方式，得到解答大约需要几秒钟：
用递归做深度搜索，限制最大深度为40级。因为只要30多级就能保证把每一个数字送到指定地方了，不必搜太多。
每当搜索到一个解答，则更新最大深度限制，保证后面的搜索不会有更多浪费。
若当前还需要继续深入搜索，则循环列出所有12种改变并进行测试。当改变发生后没有出现曾有过的重复状态，则递归搜索。
代码如下：
#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
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); // 交换指定位置上的数。};
[解决办法]
为了避免用户误以为死机，加一个进程显示在里面......有点破坏完美的感觉
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：
#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"); }}