http://poj.org/problem?id=2676
题意 ： 这个是我最喜欢玩的数独了，就是一个9乘9的宫格，填上1到9九个数字，每行每列每个宫格之内不能有重复的数字，给出的九宫格中，0是待填的数字，其他数字是已经填好的，若是无法按要求填出来，就输出原来的九宫格；
思路 ： DFS，深搜递归一下，设三个标记数组，标记一下每行的，每列的，每个宫格的，如果这个数字出现了，就标记了就行，我代码里写的是标记数组row[ i ][ j ]，代表的是第 i 行的 j 已经出现了,col[ i ][ j ]代表的是第 i 行的 j 数组存在,map[ i ][ j ]宫格 i 的 j 这个数字存在，而宫格的话大家可以自己想一下，如果一个位置的行和列是x，y，那么他所在的九宫格就应该是3*((x-1)/3)+(y-1)/3+1，但如果你往里输入的九宫格下标是从0开始的话，这个就要变成x/3*3+y/3，我也试过，但是从0开始存一直都是错的，后来就改为从一开始存了
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int row[][],col[][],map[][];//行列宫格的标记数组
int Sudoku[][];
int flag ;//标记变量
int DFS(int x,int y)
{
if(x == )
{
for(int i = ; i <= ; i++)
{
for(int j = ; j <= ; j++)
printf("%d",Sudoku[i][j]);
printf("\n");
}
return ;
}
flag = ;
if(Sudoku[x][y])//该位置原本是有数字的
{
if(y == )
flag = DFS(x+,);
else
flag = DFS(x,y+);
if(flag)
return ;
else
return ;
}
else
{
for(int i = ; i <= ; i++)
if(!row[x][i] && !col[y][i] && !map[*((x-)/)+(y-)/+][i])//如果行列宫格都没有这个数字
{
Sudoku[x][y] = i;//就填上这个数字，然后下边的行列宫格都标记为已填此数字
row[x][i]= ;
col[y][i]= ;
map[*((x-)/)+(y-)/+][i] = ;
if(y == )
flag=DFS(x+,);
else
flag=DFS(x,y+);
if(!flag)//如果没找到合适的，就全部返回原值
{
Sudoku[x][y]=;
row[x][i] = ;
col[y][i]= ;
map[*((x-)/)+(y-)/+][i]=;
}
else
return ;
}
}
return ;
}
void Init()
{
memset(row,,sizeof(row));
memset(col,,sizeof(col));
memset(map,,sizeof(map));
}
int main()
{
int i,j,n;
scanf("%d",&n);
for(int s = ; s < n ; s++)
{
Init();
for(i = ; i <= ; i++)
for(j = ; j <= ; j++)
{
scanf("%1d",&Sudoku[i][j]);
if(Sudoku[i][j])
{
row[i][Sudoku[i][j]] = ;
col[j][Sudoku[i][j]] = ;
map[*((i-)/)+(j-)/+][Sudoku[i][j]] = ;
}
}
DFS(,);
}
return ;
}