回溯算法（解任意阶数独）

<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);
                             } 
        }
}