自己写的一个数独求解程序，分享下
前些天受朋友所托写了个数独求解的程序。昨天调试了一天，算是基本搞定吧。给大家分享下。首先，是控制台的程序（vs2008）。还有就是验证了三个数独，没出现问题（不代表就没问题），
速度有点慢，做了三个都花了7秒。
就说这么多吧，程序中有诸多不足，有什么好的意见还望提出。
程序代码：//类声明文件:shudu.h
#ifndef SHUDU
#define SHUDU
class ShuDu
{
public:
ShuDu();
ShuDu(ShuDu &m);
~ShuDu();
bool InputData(); //输入数据
bool InputData(int i); //输入第i行的数据
bool SetData(int i,int j,int num); //修改数独格中某个数据
void Output()const; //输出数独格
bool GetAnswer(); //输出求解后的结果
protected:
bool IsOver(int i)const; //判断数据i是否超出了1-9的范围
bool IsRight(int i,int j,int num)const; //判断数据num是否能放置在数独格中的i,j的位置
bool IsRight(int i,int num)const; //判断数据num是否能放置在数独格中的第i的位置
bool Solve(); //求解函数
void SetP(); //根据数独格设置指针p
void Init(); //初始化数组
void Init(int i);
private:
short int data[9][9]; //存放数独的数组
short int* p; //指向一个数组，数组中存放数独要填充的位置()
short int n; //数组的个数
};
#endif
/**********************************************************/
//主文件:main.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
#include "ShuDu.h"
void main()
{
ShuDu shudu;
bool flag;
int i=0;
do
{
flag=false;
for(;i<9;i++)
{
cout<<"请输入第"<<i+1<<"行的数据(数字间以空格分隔，要填充数字的位置输入0代替)："<<endl;
if(!shudu.InputData(i))
{
cout<<"你输入了有误的数据";
cout<<"请重新输入第"<<i<<"行的数据"<<endl;
flag=true;
break;
}
}
}
while(flag);
shudu.GetAnswer();
system("pause");
}
/*******************************************************/
//类ShuDu的实现文件:shudu.cpp
#include <iostream>
#include <ctime>
using namespace std;
#include "ShuDu.h"
ShuDu::ShuDu()
{
Init();
p=NULL;
n=0;
}
ShuDu::ShuDu(ShuDu &m)
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
data[i][j]=m.data[i][j];
if(m.p!=NULL)
{
n=m.n;
p=new short int[n];
for(int i=0;i<n;i++)
p[i]=m.p[i];
}
}
ShuDu::~ShuDu()
{
if(p!=NULL)
delete[] p;
}
bool ShuDu::InputData()
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
cin>>data[i][j];
if(data[i][j]==0)
n++;
if(data[i][j]!=0&&IsOver(data[i][j]))
{
n=0;
Init();
return false;
}
}
return true;
}
bool ShuDu::InputData(int i)
{
if(i<0||i>=9)
return false;
for(int j=0;j<9;j++)
{
cin>>data[i][j];
if(data[i][j]==0)
n++;
if(data[i][j]!=0&&IsOver(data[i][j]))
{
n=0;
Init(i);
return false;
}
}
return true;
}
bool ShuDu::IsOver(int i) const
{
if(i<=0||i>9)
return true;
return false;
}
bool ShuDu::IsRight(int i,int j,int num) const
{
for(int m=0;m<9;m++)
{
if(data[i][m]!=0&&m!=j&&data[i][m]==num)
return false;
if(data[m][j]!=0&&m!=i&&data[m][j]==num)
return false;
}
int m=i/3*3;
int m1=m+3;
for(;m<m1;m++)
{
int n=j/3*3;
int n1=n+3;
for(;n<n1;n++)
{
if(data[m][n]!=0&&m!=i&&n!=j&&data[m][n]==num)
return false;
}
}
return true;
}
bool ShuDu::IsRight(int i,int num)const
{
int m=i/9,n=i%9;
return IsRight(m,n,num);
}
void ShuDu::Output() const
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
cout<<data[i][j]<<" ";
cout<<endl;
}
}
bool ShuDu::SetData(int i,int j,int num)
{
if(i<0||i>=9)
return false;
if(j<0||j>=9)
return false;
if(IsOver(num))
return false;
data[i][j]=num;
return true;
}
void ShuDu::SetP()
{
p=new short int [n];
int count=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(data[i][j]==0)
p[count++]=i*9+j;
}
}
bool ShuDu::Solve()
{
for(int i=0;i<n;i++)
{
int j=*(data[0]+p[i]);
if(j<1)
j=1;
for(;j<=9;j++)
if(IsRight(p[i],j))
{
*(data[0]+p[i])=j;
break;
}
if(i==0&&j>9)
return false;
if(j>9)
{
*(data[0]+p[i])=0;
(*(data[0]+p[i-1]))++;
i-=2;
}
Output();
cout<<"***************"<<endl;
//system("pause");
}
return true;
}
/*
void ShuDu::Solve(int i)
{
if(i>=n)
{
Output();
return;
}
int j;
for(j=1;j<=9;j++)
if(IsRight(p[i],j))
{
*(data[0]+p[i])=j;
Solve(i+i);
}
}*/
bool ShuDu::GetAnswer()
{
SetP();
time_t t1,t2;
time(&t1);
if(Solve())
{
time(&t2);
cout<<"帮你找到了一个解"<<endl;
Output();
cout<<"程序求解时间为:"<<difftime(t2,t1)<<" 秒"<<endl;
return true;
}
else
{
time(&t2);
cout<<"此数独格无解"<<endl;
cout<<"程序求解时间为:"<<difftime(t2,t1)<<" 秒"<<endl;
return false;
}
}
void ShuDu::Init()
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
data[i][j]=0;
}
void ShuDu::Init(int i)
{
for(int j=0;j<9;j++)
data[i][j]=0;
}[ 本帖最后由 hzyzxj 于 2010-4-19 11:23 编辑 ]
