首页 > 代码库 > 回溯算法（解任意阶数独）
回溯算法（解任意阶数独）
<p>回溯算法的基本框架为</p><p> 函数名（int cnt）{ </p><p> for()</p><p> {</p><p> 赋值;</p><p> if（==）｛</p><p> ｝else{</p><p> 函数名（cnt+1);</p><p> }</p><p> 抹去; </p><p> }</p><p>}</p>/*
theme:求解数独
回溯算法
Coder:瞿鹏志
time:2015.1.11
*/
#include <iostream>
using namespace std;
#define N 9
#include <math.h>
class suduk{
private:
int sudu[N][N];
public:
suduk();
void SetSudk();//输入数独矩阵
bool Isvaild(int i,int j);
void answer(int cnt);
void Cout();
};
int main(void){
suduk qus1;
qus1.SetSudk();
qus1.Cout();
qus1.answer(0);
return 0;
}
void suduk::Cout()
{
for(int prin=0;prin<N*N;prin++){
if(prin%N == 0) {
cout<<endl;
}
cout<<sudu[prin/N][prin%N]<<" ";
}
cout<<endl;
}
suduk::suduk(){
for(int i=0;i<N*N;i++){
sudu[i/N][i%N]=0;
}
}
void suduk::SetSudk()
{
int sudo[N][N]={{8,0,0,1,3,7,0,0,0},{6,0,0,9,0,0,0,1,0},{5,0,0,0,0,0,0,3,0},
{0,0,0,3,8,0,0,0,9},{0,5,0,0,0,0,0,0,0},{9,0,0,0,0,0,8,7,0},{0,2,0,0,0,0,0,0,0},
{0,0,0,0,0,6,2,4,3},{1,0,0,0,5,0,9,0,0}};
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
sudu[i][j]=sudo[i][j];
//cin>>sudu[i][j];
}
}
}
bool suduk::Isvaild(int i,int j)
{
int run;
for(run=0;run<N;run++){
if((run!=j)&&sudu[i][run]==sudu[i][j]){
return false;
}
if((run!=i)&&sudu[run][j]==sudu[i][j]){
return false;
}
}
int jie=(int)pow((double)N,1.0/2.0);
int row=i/jie*jie,col=j/jie*jie;
for(run=0;run<N;run++){
if(row+run/jie!=i || col+run%jie != j){
if(sudu[row+run/jie][col+run%jie]==sudu[i][j]){
return false;
}
}
}
return true;
}
void suduk::answer(int cnt)
{
int i=cnt/N;
int j=cnt%N;
if(sudu[i][j]==0){
for(int num=1;num<=N;num++){
sudu[i][j]=num;
if(Isvaild(i,j)){
if(cnt!=N*N-1){
answer(cnt+1);
}else{
Cout();
}
}
sudu[i][j]=0;
}
}else{
answer(cnt+1);
}
}回溯算法的基本框架为
函数名（int cnt）{
for()
{
if（）｛
｝else{
函数名（cnt+1);
}
}
}
回溯算法（解任意阶数独）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。