| Time Limit: 2000MS | Memory Limit: 65536K | |||
| Total Submissions: 16444 | Accepted: 8035 | Special Judge | ||
Description
Input
Output
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
Source
题意：每行每列每个小的九宫格 每个数字只出现一次；
看着很高大上的题目做起来这么好玩，搜索真是很神奇！应该是第一次写带有返回值的搜索
转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1303713313
大致题意：
九宫格问题，也有人叫数独问题
把一个9行9列的网格，再细分为9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。
0是待填位置，其他均为已填入的数字。
要求填完九宫格并输出（如果有多种结果，则只需输出其中一种）
如果给定的九宫格无法按要求填出来，则输出原来所输入的未填的九宫格
解题思路：
DFS试探，失败则回溯
用三个数组进行标记每行、每列、每个子网格已用的数字，用于剪枝
bool row[10][10]; //row[i][x] 标记在第i行中数字x是否出现了
bool col[10][10]; //col[j][y] 标记在第j列中数字y是否出现了
bool grid[10][10]; //grid[k][x] 标记在第k个3*3子格中数字z是否出现了
row 和 col的标记比较好处理，关键是找出grid子网格的序号与 行i列j的关系
即要知道第i行j列的数字是属于哪个子网格的
首先我们假设子网格的序号如下编排：
由于1<=i、j<=9，我们有： （其中“/”是C++中对整数的除法）
令a= i/3 , b= j/3 ，根据九宫格的 行列 与 子网格 的 关系，我们有:
不难发现 3a+b=k
即 3*(i/3)+j/3=k
又我在程序中使用的数组下标为 1~9，grid编号也为1~9
因此上面的关系式可变形为 3*((i-1)/3)+(j-1)/3+1=k
有了这个推导的关系式，问题的处理就变得非常简单了，直接DFS即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std;
int row[][],col[][],grid[][];
int g[][];
bool dfs(int x,int y)
{
if(x == )
{
return true;
}
bool flag = false;
if(g[x][y])
{
if(y == )
{
flag = dfs(x + , );
}
else
{
flag = dfs(x, y + );
}
if(flag)
return true;
else
return false;
}
else if(g[x][y] == )
{
for(int i = ; i <= ; i++)
{
int k = (x - ) / * + (y - ) / + ;
if(col[y][i] == && row[x][i] == && grid[k][i] == )
{
g[x][y] = i;
col[y][i] = ;
row[x][i] = ;
grid[k][i] = ;
if(y < )
{
flag = dfs(x,y + );
}
else
{
flag = dfs(x + , );
}
if(flag == false)
{
g[x][y] = ;
col[y][i] = ;
row[x][i] = ;
grid[k][i] = ;
}
else
return true;
}
}
}
return false;
}
int main()
{
int t;
scanf("%d", &t);
getchar();
while(t--)
{
memset(row,,sizeof(row));
memset(col,,sizeof(col));
memset(grid,,sizeof(grid));
memset(g,,sizeof(g));
char ch;
for(int i = ; i <= ; i++)
{
for(int j = ; j <= ; j++)
{
scanf("%c", &ch);
if(ch != '')
{
g[i][j] = ch - '';
row[i][ch - ''] = ;
col[j][ch - ''] = ;
int k = (i - ) / * + (j - ) / + ;
grid[k][ch - ''] = ;
}
}
getchar();
}
dfs(,);
for(int i = ; i <= ; i ++)
{
for(int j = ; j <= ; j++)
{
printf("%d",g[i][j]);
}
printf("\n");
}
}
return ;
}