洛谷P1074《靶型数独》

发表于 |

基于常识的搜索顺序优化

题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 99 格宽×99 格高的大九宫格中有99 个 33 格宽×33 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 11 到 99的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（黄色区域）为 1010 分，黄色区域外面的一圈（红色区域）每个格子为99分，再外面一圈（蓝色区域）每个格子为88 分，蓝色区域外面一圈（棕色区域）每个格子为77分，最外面一圈（白色区域）每个格子为66分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

输入格式

一共 99 行。每行99个整数（每个数都在 0-90−9 的范围内），表示一个尚未填满的数独方格，未填的空格用“00”表示。每两个数字之间用一个空格隔开。

输出格式

输出共 11 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1−1。

输入输出样例

输入 #1复制

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

输出 #1复制

1
2829

输入 #2复制

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

输出 #2复制

1
2852

解析

拿到题目：
这啥啊。。。不是很会啊。。。暴搜估计搜不过去啊。。。

无奈之下看了一眼题解，忽然就想起来了自己以前填数独的技巧。

填数独有一个技巧，就是提前填工作量最小的地方，也就是优先填数最满的地方

确定这个搜索顺序之后这个题就差不多做完了

分别开三个数组记录这一行某一个数字是否被填过，这一列某一个数字是否被填过，这一个宫是否被填过

每次搜索记录当前搜到了哪个点，枚举当前格子是填 1-9 中哪个数字，搜一搜就好了

搜索顺序如何求出？
再开俩数组分别记录每一行填了多少数字，每一列填了多少数字，转移时先枚举填的数字最多的行，然后在这一行中确定没填过的格子对应的填的数字最多的列，下一次搜索的时候就搜行列相交处的格子

建议配合代码理解

代码实现

我写完代码之后才发觉 line 和 row 都是「行」的意思。。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 9 + 2;
const int weight[11][11] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
        {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
        {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
        {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
        {0, 6, 7, 8, 9,10, 9, 8, 7, 6},
        {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
        {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
        {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
        {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
};
const int area[11][11] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
        {0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
        {0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
        {0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
        {0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
        {0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
        {0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
        {0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
        {0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
};

struct Order {
    int id, siz;
    Order(int _id = 0, int _siz = 0) : id(_id), siz(_siz) {}
    bool operator < (const Order &that) const {
        return siz > that.siz;
    }
} order[MAXN];

int n = 9, sd[MAXN][MAXN], linesiz[MAXN], rowsiz[MAXN];
bool lineUsed[MAXN][10], rowUsed[MAXN][10], areaUsed[MAXN][10];
int ans = 0, vis = 0;

void print() {
    puts("");
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            printf("%d%c", sd[i][j], j == n ? '\n' : ' ');
        }
    }
    puts("");
}

void placeNum(int x, int y, int num) {
    sd[x][y] = num;
    ++linesiz[x]; ++rowsiz[y];
    lineUsed[x][num] = rowUsed[y][num] = true;
    areaUsed[area[x][y]][num] = true;
}
void displaceNum(int x, int y, int num) {
    sd[x][y] = 0;
    --linesiz[x]; --rowsiz[y];
    lineUsed[x][num] = rowUsed[y][num] = false;
    areaUsed[area[x][y]][num] = false;
}

void DFS(int line = 0, int row = 0, int totalPlaced = 0) {
    if (totalPlaced == 81) {
        vis = 1;
        int fans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                fans += sd[i][j] * weight[i][j];
            }
        }
//        print();
//        cout << fans << endl;
        ans = std::max(ans, fans);
        return;
    }
    for (int num = 1; num <= 9; ++num) {
        if (lineUsed[line][num]
        || rowUsed[row][num]
        || areaUsed[area[line][row]][num]) continue;
        placeNum(line, row, num);
        int nextLine = 0, maxSize = -1;
        for (int i = 1; i <= n; ++i) {
            if (maxSize < linesiz[i] && linesiz[i] != 9) {
                maxSize = linesiz[i]; nextLine = i;
            }
        }
        int nextRow = 0; maxSize = -1;
        for (int i = 1; i <= n; ++i) {
            if (maxSize < rowsiz[i] && !sd[nextLine][i]) {
                maxSize = rowsiz[i]; nextRow = i;
            }
        }
//        printf("\nModified <%d,%d>: %d\n", line, row, sd[line][row]);
//        print();
        DFS(nextLine, nextRow, totalPlaced + 1);
        displaceNum(line, row, num);
    }
}

int main() {
    int maxSiz1 = -1, lc = 0, maxSiz2 = -1, rc = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sd[i][j] = getint();
            if (sd[i][j] == 0) continue;
            cnt += (sd[i][j] > 0);
            linesiz[i] += (sd[i][j] > 0);
            rowsiz[j] += (sd[i][j] > 0);
            lineUsed[i][sd[i][j]]
            = rowUsed[j][sd[i][j]] = true;
            areaUsed[area[i][j]][sd[i][j]] = true;
        }
        if (maxSiz1 < linesiz[i] && linesiz[i] != 9) {
            lc = i; maxSiz1 = linesiz[i];
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (maxSiz2 < rowsiz[i] && !sd[lc][i]) {
            rc = i; maxSiz2 = rowsiz[i];
        }
    }
    DFS(lc, rc, cnt);
    if (!vis) puts("-1");
    else printf("%d\n", ans);
    return 0;
}