(((silence)))

写了个算法，杀你用的！

首先检查一遍，把一眼能看出来的空填上，然后用回溯法进行搜索，这就是算法的思路了

哎，费了我多少心血啊~

贴出来，大家用来和数独打架吧。只要他有解，俺们一定能以很快很快的速度解出——目前的设定是只要找出一个解就停下（因为正规的数独有且仅有一个解），而稍稍改动就可以让他求出所有的解。（我似乎有做记号）

//版权所有，翻录不究。但翻录时如果说一下是从俺们这儿看到的，I will appreciate it
class sudoku
{
 char board_map [9][9];//盘面
 char background[9][9];//临时的盘面
 bool possible  [9][9][10];  //某个格子里某个元素是否可能出现
 char remaind   [9][9];  //某个格子中还有几种可能的数字
 void init()
 {
  for(int i=0;i<9;i++)
  { 
   for(int j=0;j<9;j++)
   {
    remaind[i][j]=9;
    for(int k=0;k<=9;k++)possible[i][j][k]=true;
    background[i][j]=0;
   }
  }
 }
 public:
 sudoku(char b[9][9])
 {
  init();
  for(int i=0;i<9;i++)
   for(int j=0;j<9;j++)
    {
     board_map[i][j]=b[i][j];
     background[i][j]=0;
    }
 }
 sudoku()
 {
  init();
  for(int i=0;i<9;i++)
   for(int j=0;j<9;j++)
    background[i][j]=board_map[i][j]=0;
 }
 ~sudoku(){}
 
 void reset(char b[9][9])
 {
  init();
  for(int i=0;i<9;i++)
   for(int j=0;j<9;j++)
    {
     board_map[i][j]=b[i][j];
     background[i][j]=0;
    }
 }
 
 void get_result(char b[9][9])
 {for(int x=0;x<9;x++)for(int y=0;y<9;y++)b[x][y]= board_map[x][y];}
 private:
 void scan(int x,int y,int n);
 bool trace_back();
 public:
 bool search();
};

void sudoku::scan(int x,int y,int n)
{
 //cout<<"scaning ---> "<<x+1<<','<<y+1<<':'<<n<<'\n';
 if(board_map[x][y]==0) return;
 int i,j,k;
 int box_x=int(x/3) , box_y=int(y/3);
 
//---------------------------------------------------------------------------------
 
 for(i=0;i<9;i++)
 {
  if(possible[i][y][n])
  {
   possible[i][y][n] = false;
   if(remaind[i][y]!=1) remaind[i][y]--;
   if(remaind[i][y]==1 && board_map[i][y]==0)
   {
    for(k=1;k<=9;k++)if(possible[i][y][k]){background[i][y]=k;break;}
   }
  }
 }
 for(j=0;j<9;j++)
 {
  if(possible[x][j][n])
  {
   possible[x][j][n] = false;
   if(remaind[x][j]!=1) remaind[x][j]--;
   if(remaind[x][j]==1 && board_map[x][j]==0)
   {
    for(k=1;k<=9;k++)if(possible[x][j][k]){background[x][j]=k;break;}
   }
  }
 }
 for(i=box_x*3;i<box_x*3+3;i++)
  for(j=box_y*3;j<box_y*3+3;j++)
  {
   if(possible[i][j][n])
   {
    possible[i][j][n] = false;
    if(remaind[i][j]!=1) remaind[i][j]--;
    if(remaind[i][j]==1 && board_map[i][j]==0)
    {
     for(k=1;k<=9;k++)if(possible[i][j][k]){background[i][j]=k;break;}
    }
   }
  }
 for(k=0;k<=9;k++) possible[x][y][k] = false;
 possible[x][y][n]=true;
 remaind [x][y]=0;
 
//---------------------------------------------------------------------------------
 
 int p=0;
 int ti,tj,tk;
 for(k=1;k<=9;k++)
 {
  p=0;
  for(i=0;i<9;i++)
  {
   if(possible[i][y][k])
   {
    p++;
    ti=i;
    tk=k;
   }
  }
  if(p==1) background[ti][y]=tk;
 }
 
 for(k=1;k<=9;k++)
 {
  p=0;
  for(j=0;j<9;j++)
  {
   if(possible[x][j][k])
   {
    p++;
    tj=j;
    tk=k;
   }
  }
  if(p==1) background[x][tj]=tk; 
 }
 
 for(k=1;k<=9;k++)
 {
  p=0;
  for(i=box_x*3;i<box_x*3+3;i++)
   for(j=box_y*3;j<box_y*3+3;j++)
   {
    if(possible[i][j][k])
    {
     p++;
     ti=i;
     tj=j;
     tk=k;
    }
   }
  if(p==1) background[ti][tj]=tk;     
 }
}

bool sudoku::trace_back()//用回溯法进行搜索！
{
 int x=0,y=0,k,n;
 bool find_one=false;

 bool in_column[9][10];//true=>能放入第n行
 bool in_row[9][10];   //true=>能放入第n列
 bool in_box[3][3][10];//true=>能放入第n个格子
 for(n=1;n<=9;n++)//初始化三个可恶的数组
  for(x=0;x<9;x++)
  {
   in_column[x][n]=true;
   in_row[x][n]=true;
   in_box[x/3][x%3][n]=true;
  }
 
 for(n=1;n<=9;n++)
 for(x=0;x<9;x++)
  for(y=0;y<9;y++)
  {
   if(board_map[x][y]==n)
   {
    in_column[x][n]=false;
    in_box[x/3][y/3][n]=false;
    in_row[y][n]=false;
   }
  }
  
 x=0,y=0; 

 while(true)
 {
  if (x<0||y<0)//找到了所有结果
   break;
  if (x>8||y>8)//找到了一个结果
   break;
  
  while(board_map[x][y]!=0)//到下一个非预设点
  {
   if(++x==9)
   {
    x=0;
    ++y;
   }
   if(y>8) break;
   }  
   
   find_one=false;
  for(n=background[x][y]+1;n<=9;n++)
   if (
    in_column[x][n]&&
    in_row[y][n]&&
    in_box[x/3][y/3][n]
    )//可以放入
   {
    if((k=background[x][y])!=0)
    {
     in_column[x][k]=true;
     in_row[y][k]=true;
     in_box[x/3][y/3][k]=true;
    }
    
    background[x][y]=n;
    
    in_column[x][n]=false;
    in_row[y][n]=false;
    in_box[x/3][y/3][n]=false;
    
    find_one=true;
    break;
   }
  
  if(find_one)
  {
   do //到下一个非预设点
   {
    if(++x==9)
    {
     x=0;
     ++y;
    }
    if(y>8) break;
    } while(board_map[x][y]!=0);
  }
  else
  {//惨了走不动了,那就回去吧！
   
   in_column[x][background[x][y]]=true;
   in_row[y][background[x][y]]=true;
   in_box[x/3][y/3][background[x][y]]=true;
   
   background[x][y]=0;
   do
   {
    if(--x<0)
    {
     x=8;
     --y;
    }
    if(y<0)break;
   }while(board_map[x][y]!=0);
  }
 }
 
 int sum=0;
 for(x=0;x<9;x++)for(y=0;y<9;y++)
 {
  if(background[x][y]!=0)board_map[x][y]=background[x][y];
  sum+=board_map[x][y];
 }
 if (sum==45*9) return true;
 else return false;
}

bool sudoku::search()
{
 bool find_ans=false,new_ans_finded;
 int x,y;
 for(x=0;x<9;x++)
  for(y=0;y<9;y++)
   scan(x,y,board_map[x][y]);
 do
 {
  new_ans_finded=false;
  for(x=0;x<9;x++)
   for(y=0;y<9;y++)
   {
    if (background[x][y]!=0&&board_map[x][y]==0)
    {
     new_ans_finded=true;
     board_map[x][y]=background[x][y];
     scan(x,y,board_map[x][y]);
     //cout<<"* finded:"<<x+1<<','<<y+1<<':'<<(int)background[x][y]<<'\n';
    }
   }
 }
 while (new_ans_finded);
 unsigned int sum=0;
 for(x=0;x<9;x++)for(y=0;y<9;y++)sum+=board_map[x][y];
 if (sum==45*9) return true;
 else return trace_back();//此路不通，换一条试试！
}

这是类！窗体程序和控制台程序都能用的！

再给出一个简单的控制台主函数：

int main()
{

 char s[4][9][9]=
 {
  0,2,0, 0,0,0, 0,0,0,
  0,0,1, 5,0,0, 0,0,2,
  0,6,0, 7,0,0, 0,0,0,
  
  1,0,0, 3,0,0, 0,0,0,
  0,7,8, 0,0,2, 0,0,0,
  0,0,5, 0,9,0, 0,0,3,
  
  7,0,4, 0,0,0, 0,8,6,
  0,0,0, 0,3,0, 5,1,0,
  0,0,0, 4,1,0, 0,0,0
  
,       ////////////////////

  0,0,0, 0,4,0, 2,8,0,
  0,0,4, 0,0,1, 0,7,0,
  0,9,0, 0,0,8, 1,3,0,
  
  0,0,7, 0,6,0, 0,0,1,
  0,6,0, 0,7,4, 0,0,8,
  0,4,0, 0,0,5, 6,0,0,
  
  1,0,3, 0,0,0, 0,0,5,
  4,0,0, 0,1,0, 8,0,0,
  2,0,6, 0,0,7, 0,0,0
  
,       ////////////////////

  0,0,6, 0,0,0, 0,0,0,
  0,0,0, 0,0,0, 0,0,8,
  0,0,2, 4,0,1, 0,0,0,
  
  0,0,4, 0,0,0, 0,0,0,
  0,3,0, 0,8,0, 0,0,5,
  0,0,0, 0,0,9, 0,0,0,
  
  5,8,0, 0,7,0, 0,0,0,
  0,0,0, 0,0,0, 0,0,0,
  0,7,0, 0,0,3, 4,1,0
  
,       ////////////////////

  0,0,0, 6,0,0, 0,4,0,
  3,2,0, 0,0,0, 0,0,1,
  0,4,8, 0,0,1, 3,0,0,
  
  0,0,0, 5,0,0, 0,7,0,
  8,3,0, 0,1,0, 0,0,5,
  5,0,7, 0,0,6, 1,0,0,
  
  1,5,0, 0,0,8, 6,0,0,
  0,0,0, 0,0,0, 0,0,0,
  4,8,0, 0,0,9, 7,0,0
 };

 sudoku x;
 char t[9][9];
 for(int n=0;n<4;n++)
 {
  x.reset(s[n]);
  if(x.search()) cout<<"answer finded:\n";
  else cout<<"can't find answer\n";
  x.get_result(t);
  
  
  for(int i=0;i<9;i++)
  {
   if(i==0)cout<<"┏━┯━┯━┳━┯━┯━┳━┯━┯━┓\n┃";
   else if(i%3==0)cout<<"┣━┿━┿━╋━┿━┿━╋━┿━┿━┫\n┃";
   else cout<<"┠─┼─┼─╂─┼─┼─╂─┼─┼─┨\n┃";
   for(int j=0;j<9;j++)cout<<(s[n][i][j]?'*':' ')<<int(t[i][j])<<((j+1)%3!=0?"│":"┃");
   cout<<'\n';
  }
  cout<<"┗━┷━┷━┻━┷━┷━┻━┷━┷━┛\n";
 }
 cin.get();
 return 0;
}

他的运行结果如图：