POJ2676Sudoku

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 ;

}