九宫格A*程序代码

急求九宫格A*程序代码，在线等

http://www.stl.vc/htmlx/Theory/Examples/2009/1018/4061.html

给你地址

这个只要你搞清数学模型，下来就顺理成章了~

#include <iostream>
#include<time.h>
using namespace std;

C++编程网

int pu[9][9]=
{
{0,0,6,5,0,0,0,0,0},
{8,0,9,1,0,4,0,7,0},
{0,0,3,0,0,0,2,4,0},
{0,8,7,4,0,3,9,6,5},
{0,9,0,7,0,0,0,1,0},
{4,0,1,0,0,9,7,8,0},
{0,6,0,0,8,0,1,0,7},
{9,7,2,3,4,1,6,5,8},
{0,1,8,0,6,0,4,3,0} }; 内容来自www.stl.vc

int isvalid(const int i, const int j)//验证函数当期i,j坐标是否符合游戏规则，不重复
{
const int n = pu[i][j];
const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
int t, u; www.stl.vc

for (t = 0; t < 9; t++)
if (t != i && pu[t][j] == n || t != j && pu[i][t] == n)//0-9的数字，每行每列都不能重复
return 0; 内容来自www.stl.vc

for (t = query[i]; t < query[i] + 3; t++) //9个宫的3×3里也不能重复
for (u = query[j]; u < query[j] + 3; u++)
if ((t != i || u != j) && pu[t][u] == n)
return 0;

本文来自C++编程网

return 1;
}

www.stl.vc

void output(void)//输出函数
{
static int n; 本文来自C++编程网

cout << "Solution " << ++n << ":" <<endl;

www.stl.vc

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout<< pu[i][j] << " ";
cout << endl;
} 本文来自C++编程网

cout << endl;
} 内容来自www.stl.vc

void Try(const int n)//核心函数，回溯算法
{
if (n == 81) {//是否已经是最后一个格子
output();
return;
}

C++编程网

const int i = n / 9, j = n % 9;

C++编程网

if (pu[i][j] != 0) {//如果当前格子不需要填数字，就跳到下一个格子
Try(n + 1);
return;
}

for (int k = 0; k < 9; k++) {
pu[i][j]++;//当前格子进行尝试所有解
if (isvalid(i, j))
Try(n + 1);//验证通过，就继续下一个
}

pu[i][j] = 0; //如果上面的单元无解，就回溯
} 本文来自C++编程网

int main(void)
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
cin>>pu[i][j]; C++编程网

long start=clock();
Try(0);
long end=clock();
cout<<"计算一共花了"<<(double)(end-start)<<"毫秒"<<endl;
return 0;
} www.stl.vc

www.stl.vc