Sudoku Killer

发表于 | 分类于 | 评论数：

据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品：HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。

所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。

数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。

输入格式

本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。

输出格式

对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。对于每组测试数据保证它有且只有一个解。

输入样例

7  1  2  ?  6  ?  3  5  8
?  6  5  2  ?  7  1  ?  4
?  ?  8  5  1  3  6  7  2
9  2  4  ?  5  6  ?  3  7
5  ?  6  ?  ?  ?  2  4  1
1  ?  3  7  2  ?  9  ?  5
?  ?  1  9  7  5  4  8  6
6  ?  7  8  3  ?  5  1  9
8  5  9  ?  4  ?  ?  2  3

输出样例

7  1  2  4  6  9  3  5  8
3  6  5  2  8  7  1  9  4
4  9  8  5  1  3  6  7  2
9  2  4  1  5  6  8  3  7
5  7  6  3  9  8  2  4  1
1  8  3  7  2  4  9  6  5
2  3  1  9  7  5  4  8  6
6  4  7  8  3  2  5  1  9
8  5  9  6  4  1  7  2  3

题目题解

数独的基本规则是只能填1 - 9这九个数字。且行、列、九方格都不能有相同的数字。
在输入数据时找到?的位置并用数组保存起来。比如vis[0][0]便是代表第一个?号的横坐标，而vis[0][1]则是代表第一个?的纵坐标，之后要做的就是把所有的?号填完。

在判断的过程注意一下找到对应?的九方格起始位置
注意输出格式，两组解中间都需要换行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstring>
using namespace std;

int map[10][10], vis[85][5], cnt;
bool flag;

bool check(int k, int n) {
    for (int i = 0; i < 9; i++) {
        if (map[i][vis[n][1]] == k || map[vis[n][0]][i] == k)
            return false;
    }

    int x = vis[n][0] / 3 * 3;
    int y = vis[n][1] / 3 * 3;
    
    for (int i = x; i < x + 3; i++) {
        for (int j = y; j < y + 3; j++) {
            if (map[i][j] == k)
                return false;
        }
    }

    return true;
}

void dfs(int n) {
    if (flag == true)
        return;
    
    if (n == cnt) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (j == 8) 
                    cout << map[i][j] << endl;
                else
                    cout << map[i][j] << " ";
            }
        }
        flag = true;
    }
    
    for (int k = 1; k <= 9; k++) {
        int i = vis[n][0], j = vis[n][1];
        if (check(k, n) == true) {
            map[i][j] = k;
            dfs(n + 1);
            map[i][j] = 0;
        }
    }
}

int main() {
    int f = 0;
    char c;
    while (cin >> c) {
        cnt = 0;
        flag = false;
        
        memset(vis, 0, sizeof vis);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ((i == 0 && j == 0) {
                    if (c == '?') {
                    map[i][j] = 0;
                    vis[cnt][0] = i;
                    vis[cnt ++][1] = j;
                    }
                    else
                        map[i][j] = c - '0';
                }
                else {
                    cin >> c;
                    if (c == '?') {
                    map[i][j] = 0;
                    vis[cnt][0] = i;
                    vis[cnt ++][1] = j;
                    }
                    else
                        map[i][j] = c - '0';
                }
            }
        }
        //输出格式要求
        if (f ++)   cout << endl;
        dfs(0);
    }

    return 0;
}