计蒜客-数独
蒜头君今天突然开始还念童年了,想回忆回忆童年。他记得自己小时候,有一个很火的游戏叫做数独。便开始来了一局紧张而又刺激的高阶数独。蒜头君做完发现没有正解,不知道对不对? 不知道聪明的你能否给出一个标准答案?
标准数独是由一个给与了提示数字的 9×9 网格组成,我们只需将其空格填上数字,使得每一行,每一列以及每一个 3×3 宫都没有重复的数字出现。
输入:
* 2 6 * * * * * * * * * 5 * 2 * * 4 * * * 1 * * * * 7 * 3 * * 2 * 1 8 * * * * 3 * 9 * * * * 5 4 * 1 * * 7 * 5 * * * * 1 * * * 6 * * 9 * 7 * * * * * * * * * 7 5 *
输出:
1 2 6 7 3 4 5 9 8 3 7 8 5 9 2 6 1 4 4 9 5 1 6 8 2 3 7 7 3 9 4 2 5 1 8 6 8 6 1 3 7 9 4 2 5 2 5 4 8 1 6 3 7 9 5 4 7 2 8 1 9 6 3 6 1 3 9 5 7 8 4 2 9 8 2 6 4 3 7 5 1
思路:把所有需要填数的位置保存,然后对这些位置进行DFS,然后检查深搜时的位置是否每一行,每一列,每一个3*3的九宫格都符合条件
提醒:两个数字之间要有一个空格,其他地方不要输出多余的符号
/*
思路:先判断同一行和同一列,然后在判断每一个3*3九宫格中是否有重复数字
,这该如何判断呢,我给这9个3*3的九宫格编号,利用每个格子的坐标(最好从0开始,
这样更好编号)来编号,然后存储在数组中,只需判断每个编号中是否有数字重复即可
*/
#include<iostream>
using namespace std;
char map[10][10];
int n = 0;
int flag = 0;
int row[99];
int col[99];
int book[10][10] = {0};
void print()
{
for(int i = 1;i <= 9;++i)
{
for(int j = 1;j <= 9;++j)
{
if(j == 1)
cout << map[i][j];
else
cout << " " << map[i][j];
}
cout << endl;
}
}
bool check(int cnt,char num)
{
//检查行
for(int i = 1;i <= 9;++i)
{
if(i == col[cnt]) continue;
if(map[row[cnt]][i] == num)
return false;
}
//检查列
for(int i = 1;i <= 9;++i)
{
if(i == row[cnt]) continue;
if(map[i][col[cnt]] == num)
return false;
}
return true;
}
void dfs(int cnt)
{
if(flag) return ;
if(cnt == n)
{
print();
flag = 1;
return ;
}
for(int i = 1;i <= 9;++i)
{
int x1 = (row[cnt]-1)/3;
int x2 = (col[cnt]-1)/3;
int x3 = x1*3+x2;
if(check(cnt,i+'0') && !book[x3][i]){
book[x3][i] = 1;
map[row[cnt]][col[cnt]] = i+'0';
dfs(cnt+1);
map[row[cnt]][col[cnt]] = '*';
book[x3][i] = 0;
}
}
}
int main()
{
for(int i = 1;i <= 9;++i)
{
for(int j = 1;j <= 9;++j)
{
cin >> map[i][j];
//这里是为了计算编号,所以把横纵-1
int k1 = i-1;
int k2 = j-1;
int x1 = k1/3;
int x2 = k2/3;
int num = x1*3+x2;
if(map[i][j] == '*')
{
row[n] = i;
col[n++] = j;
}
else
book[num][map[i][j]-'0']++;
}
}
dfs(0);
return 0;
}