#include<iostream>
using namespace std; bool heng(int **sudo, int a, int b, int value)
{
bool flag = true;
for(int i=0; i<9; i++)
{
if(sudo[a][i]==value)
{
flag = false;
}
}
return flag;
} bool shu(int **sudo, int a, int b, int value)
{
bool flag = true;
for(int i=0; i<9; i++)
{
if(sudo[i][b]==value)
{
flag = false;
}
}
return flag;
} bool fang(int **sudo, int a, int b, int value)
{
bool flag = true;
int x = a/3*3;
int y = b/3*3; for(int i = 0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(sudo[x+i][y+j]==value)
{
flag = false;
}
}
}
return flag;
} void dfs(int a, int b, int **sudo, bool &flag)
{
if(a==9 && b==0)
{
for(int i=0; i<9; i++)
{
for(int j=0; j<8; j++)
{
cout<<sudo[i][j]<<' ';
}
cout<<sudo[i][8]<<endl;
}
flag = false;//find
return;
}
else
{
if(flag)
{
if(sudo[a][b]==0)
{
for(int i=1; i<=9; i++)
{
if(flag && heng(sudo, a, b, i) && shu(sudo ,a, b,i) && fang(sudo, a, b, i))
{
sudo[a][b] = i;
dfs( (b==8)?a+1:a, (b==8)?0:b+1, sudo, flag);
sudo[a][b] = 0;
}
}
}
else
{
dfs( (b==8)?a+1:a, (b==8)?0:b+1, sudo, flag);
}
}
else
{
return ;
}
}
} int main()
{
int **sudo;
sudo = new int* [9];
for(int i=0; i<9; i++)
{
sudo[i] = new int [9];
} for(int i=0; i<9; i++)
{
for(int j=0; j<9; j++)
{
cin>>sudo[i][j];
}
} //dfs
bool flag = true;
dfs(0,0,sudo, flag); for(int i=0; i<9; i++)
{
delete [] sudo[i];
}
delete [] sudo; return 0;
}
| 描述 |
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。 |
|---|---|
| 知识点 | 查找,搜索,排序 |
| 运行时间限制 | 10M |
| 内存限制 | 128 |
| 输入 |
包含已知数字的9X9盘面数组[空缺位以数字0表示] |
| 输出 |
完整的9X9盘面数组 |
| 样例输入 | 0 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 0 4 5 2 7 6 8 3 1 |
| 样例输出 | 5 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 9 4 5 2 7 6 8 3 1 |