HDOJ Sudoku Killer(dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1426

思路分析：该问题为数独问题，明显解是唯一的，所有采用dfs搜索效果更好；

在搜索时，可以通过3个数组来判断对于某个特定的数是否能够满足要求，即在每一行、每一列和每一个3X3的方块中只有唯一的1~9之间的数；

vis_r数组：如果vis_r[i][j] == 1表示在第i行中数字j已经存在,否则表示不存在；

vis_c数组：如果vis_c[i][j] == 1表示在第j列数字j已经存在，否则表示不存在；

对于3X3方块，按照从左到右，从上到下的顺序编号为0~9；

如果vis_k[i][j] == 1则表示第i号方块中数字j已经存在，否则表示不存在；

 

代码如下：

#include <cstdio>

#include <iostream>

using namespace std;

const int MAX_N = 85;

const int MAX_M = 10;

int map[MAX_M][MAX_M];

int vis_r[MAX_M][MAX_M];

int vis_c[MAX_M][MAX_M];

int vis_k[MAX_M][MAX_M];

struct Node { int x, y; };

Node arr[MAX_N];

inline int ChunkNumber(int i, int j) { return i / 3 * 3 + j / 3; }

void Dfs(int deep, int k, int &find_ans)

{

    if (deep == k)

    {

        find_ans = 1;

        return;

    }

    else

    {

        int x = arr[deep].x;

        int y = arr[deep].y;

        int num_chunk = ChunkNumber(x, y);

        for (int i = 1; i <= 9; ++i)

        {

            if (!vis_r[x][i] && !vis_c[y][i] && !vis_k[num_chunk][i])

            {

                map[x][y] = i;

                vis_r[x][i] = 1;

                vis_c[y][i] = 1;

                vis_k[num_chunk][i] = 1;

                Dfs(deep + 1, k, find_ans);

                if (find_ans) return;

                vis_r[x][i] = 0;

                vis_c[y][i] = 0;

                vis_k[num_chunk][i] = 0;

                map[x][y] = 0;

            }

        }

    }

}

int main()

{

    char temp[MAX_M][MAX_M];

    int k = 0, find_ans = 0;

    int flag = 0;

    while (scanf("%s", &temp[0][0]) != EOF)

    {

        k = find_ans = 0;

        for (int j = 1; j < 9; ++j)

            scanf("%s", &temp[0][j]);

        for (int i = 1; i < 9; ++i)

            for (int j = 0; j < 9; ++j)

                scanf("%s", &temp[i][j]);

        memset(vis_r, 0, sizeof(vis_r));

        memset(vis_c, 0, sizeof(vis_c));

        memset(vis_k, 0, sizeof(vis_k));

        for (int i = 0; i < 9; ++i)

        {

            for (int j = 0; j < 9; ++j)

            {

                if (temp[i][j] == '?')

                {

                    map[i][j] = 0;

                    arr[k].x = i;

                    arr[k].y = j;

                    k++;

                }

                else

                {

                    int num = 0;

                    num = map[i][j] = temp[i][j] - '0';

                    vis_r[i][num] = 1;

                    vis_c[j][num] = 1;

                    vis_k[ChunkNumber(i, j)][num] = 1;

                }

            }

        }

        Dfs(0, k, find_ans);

        if (flag)

            printf("\n");

        else

            flag = 1;

        for (int i = 0; i < 9; ++i)

            for (int j = 0; j < 9; ++j)

            {

                if (j != 8)

                    printf("%c ", map[i][j] + '0');

                else

                    printf("%c\n", map[i][j] + '0');

            }

        }

    return 0;

}