c++递归解数独方法示例_C 语言

复制代码 代码如下:

#include<iostream>

using namespace std;

void init();
void function(int m);
int canplace(int row,int col,int c);
void outputresult();

int a[9][9], maxm = 0;

int main()
{ 
 init();
 function(0);
 return 0;
}
void init()
{
 int i, j;
 for(i = 0; i < 9; i++)
 {
  for(j = 0; j < 9; j++)
  {
   cin >> a[i][j];
  }
 }
}
void function(int m)
{
 int i, j, row, col;
 if (m >= 81)
 {
  outputresult();
 }
 else
 {
  row = m / 9;
  col = m % 9;
  if(a[row][col] != 0)
  {
   function(m+1);
  }
  for(i = 1; i <= 9; i++)
  {
   if(canplace(row,col,i) == 1)
   {
    a[row][col] = i;
    function(m + 1);
    a[row][col] = 0;
   }
  }

 }
}
int canplace(int row,int col,int c)
{
 int i, j;
 int flag = 1;

 for(i = 0; i < 9; i++ )
 {
  if(a[row][i] == c || a[i][col] == c)
  {
   flag = 0;
   break;
  }
 }
 if(flag != 0)
 {
  for(i = (row / 3) * 3; i < (row / 3) * 3 + 3; i++)
  {
   for(j = (col / 3) * 3; j < (col / 3) * 3 + 3; j++)
   {
    if(a[i][j] == c)
    {
     flag = 0;
     break;
    }
   }
   if(flag == 0)
   {
    break;
   }
  }
 }
 return flag;
}
void outputresult()
{
 int i, j;

 for(i = 0; i < 9; i++)
 {
  if(i % 3 == 0)
  {
   cout << endl;
  }
  for(j = 0; j < 9; j++)
  {
   if(j % 3 == 0)
   {
    cout << " ";
   }
   cout << a[i][j] << " ";
  }
  cout << endl;
 }
 cout << endl;
}