用C++/C写了个数独暴力破解算法,运用递归来破解数独
搞了半天不知道错哪。。求前辈指教。。
PS:数独就是9×9=81个格子
要把9组1~9一共81个数字填入格子中
要求:
每一行不能有相同的数
每一列不能有相同的数
每一小宫(9个格子)不能有相同的数
#include <iostream>
using namespace std;
void Sudoku(int x,int y); //放数
int Judge(int x,int y,int a); //判断能否放数
int Array[9][9] = { //数独
{9,0,0,0,2,0,0,0,0},
{1,0,0,0,0,6,0,4,0},
{0,6,4,0,3,0,0,0,0},
{6,9,7,0,8,0,0,0,0},
{0,4,0,1,0,0,2,0,3},
{3,0,0,0,5,0,0,0,8},
{0,0,0,0,4,0,0,3,2},
{0,7,0,3,1,0,0,0,0},
{0,1,0,0,6,8,0,9,7}
};
int main(){
Sudoku(0,0); //从(0,0)开始放数
for(int i=0;i<9;i++){ //打印
for(int j=0;j<9;j++)
cout<<Array[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return 0;
}
void Sudoku(int x,int y){
if(Array[x][y]==0){ //如果该位没数表示可以放数
int temp_A = 0; //临时变量
int temp_B = 0;
for(int a=1;a<10;a++){ //从1到9循环放数
if(Judge(x,y,a)==1){ //如果可以放数
if(x<8){ //从行放数
Array[x][y]=a; //就放数
if(Array[x+1][y]==0) //下一个是不是可放数位
temp_A=1; //是的话临时变量为1
else
temp_A=0; //不是则为0
Sudoku(x+1,y); //去下一个位子放数
if(temp_A==1) //递归回来以后,如果临时变量为1,即下一位原本是0
Array[x+1][y]=0; //将下一位置0(还原)
}
if(x==8&&y<8){ //行满了去下一列,重复上述步骤
Array[x][y]=a;
if(Array[0][y+1]==0)
temp_B=1;
else
temp_B=0;
Sudoku(0,y+1);
if(temp_B==1)
Array[0][y+1]=0;
}
}
}
}
if(Array[x][y]!=0){ //有数则直接去下一格放数
if(x<8)
Sudoku(x+1,y);
if(x==8&&y<8)
Sudoku(0,y+1);
}
}
int Judge(int x,int y,int a){
int row,len;
row = x / 3;
row = row * 3;
len = y / 3;
len = len * 3;
for(int i=0;i<9;i++){
if(a==Array[i][y])
return 0; //每列上有相同的则返回0说明不行
if(a==Array[x][i])
return 0; //每行上有相同的则返回0说明不行
}
for(int i=row;i<row+3;i++)
for(int j=len;j<len+3;j++)
if(a==Array[i][j])
return 0; //每小宫里有相同的也返回0
return 1; //通过考研就返回1说明能放
}