利用位运算验证数独正确性

数独是一种益智解谜游戏。初始状态,在 $9\times 9$ 的盘面上,零星分布着一些 1 – 9 的整数。规则要求玩家在初始状态的基础上,填入 1 – 9 的数字,使得 $9\times 9$ 的盘面上,每个横行、纵列、$3\times 3$ 宫都有完整且不重复的 1 – 9 组合。

现在的问题是,给定一个数独答案,如何用代码验证这个答案的正确性。本文使用 C++ 来实现该目标。

分析

根据规则,验证程序必然要验证 9 个横行、9 个纵列、9 个宫分别的正确性。在这个层面上,没有投机取巧的余地。因为,哪怕只省略了一个横行、纵列或是宫,都有可能造成误判——程序认为数独答案正确,但实际错误。反过来,只要程序发现有一个横行、纵列或是宫有异常,就可断定答案错误。

在行列宫的角度,数独验证的方法简单明了。但验证横行、纵列和宫中的数字组合的细节,却藏着魔鬼。

按照规则,正确的数独每一个行列宫,其中的数字组合都应当是完整且不重复的 1 – 9 的组合。这样,似乎只需验证行列宫中数字之和为 $45 = \sum_{i = 1}^{9} i$ 即可。我们称之为求和验证法。然而,这藏着一个魔鬼——求和验证法暗藏了一个假设,而这个假设不总是成立:每一个行列宫中的数字只能是 1 – 9 中的整数,并且若这一行列宫的数字组合有误,则只能是有一个数字重复一次。于是,至少有两种特殊情形能够轻易地推翻这一假设,从而推翻求和验证法。其一,数字组合 $[1, 2, 3, 4, 6, 6, 6, 8, 9]$ 中 $6$ 重复了 3 次,但整个组合的和为 45。其二,数字组合 $[0, 2, 3, 4, 5, 6, 7, 8, 10]$ 中,出现了 1 – 9 之外的数字,但整个组合的和为 45。考虑第二种情况是有意义的,因为,尽管规则要求仅使用 1 – 9 之间的整数,但是却无法保证数独答案中只有这些数字——不能对用户输入做任何假设,完全有可能出现规则之外的输入。

在讨论求和验证法时,本文指出了其暗含的假设。通过指出假设的不合理处,推翻了求和验证法。事实上,这一假设只是表象,还可以深入挖掘。

主张求和验证法的人,事实上受到了某种欺骗。数独及其要求人们以 1 – 9 的整数填充宫格的规则,看似是一个数字问题;但实际上,数独规则的核心不在「数」而在「独」。若把 1 – 9 换成任意其它 9 个符号,比如字母 A – I,不难发现也能套入数独的规则。因此,在数独中,数字仅仅是一个符号,代表不同的个体,没有运算上的价值。这也就是说,任何假定数独中数字可以运算的验证方法,都是不正确的。

考虑到数独中的数字仅仅是符号,代表不同的个体,验证程序只能从集合相等的角度进行验证。也就是说,在 C++ 中,程序要将每一个行列宫中的数字纳入一个集合,与正确的集合进行比对。若比对不符,则说明数独答案错误;否则,若所有行列宫均比对成功,则说明数独答案正确。

集合

说到集合,C++ 的标准模板库提供了 std::setstd::unordered_set 两种容器模板。按前文介绍,std::set 以平衡二叉树实现,而 std::unordered_set 以哈希表实现。因此,一个可行的方案,是以 std::setstd::unordered_set 为容器,保存每一个行列宫中的数字组合,然后与正确的集合比对。考虑到此处数字的顺序不重要,使用 std::unordered_set 更为妥当。因此,正确的集合应是:

1
2
stataic const constexpr
std::unordered_set<const uint8_t> kCorrectSet{1, 2, 3, 4, 5, 6, 7, 8, 9};

标准模板库提供了高效的容器,程序需要的集合这一数据结构已经有了着落。但标准模板库是为一般情形设计的,在绝大多数情况下,其中的设施都可堪使用,但并不一定是最优选择。在数独验证任务中,程序所需的集合总是非常小的——不超过 9 个元素(对于 9 宫格的数独来说)。在这样的数据规模下,频繁对集合进行建立、插入、比对、销毁的成本是很高的。

事实上,在数独验证这一有严格限定的问题下,集合这一数据结构的实现有更优的方案。当然,选用任何方案都会有一定的代价;而选用这一方案的代价即是:需要预先假定一种对应关系。

这一方案相关的假设如下:

  • 首先,以一个整型变量代替标准模板库中的设施,作为集合容器。
  • 其次,假定整型变量中的二进制位(bit)代表对应元素在集合中是否存在。例如若 1 在集合中,则该整型变量的倒数第 1 位(最低位)置 1,否则置 0。又例如若 4 在集合中,则该整型变量的倒数第 4 位置 1,否则置 0。

在这样的假设下,集合的操作有:

操作 方法
建立 int16_t flag = 0x0
插入(x flag or_eq (1 << (x - 1))
比较 if (kFlag == flag)

显而易见,对单个整型变量的操作,比对标准模板库的容器的操作要快至少一个数量级。

这一方案受到了 Milo Yip 的知乎答案中提到的 Optimizing software in C++ 中关于布尔变量优化(7.5 节)的启发。

实现

首先,本文给出测试文件。测试文件的第一行是一个整数,表示测试文件中有多少个数独答案。而后则是每个数独答案的具体内容。

sudoku.test.txt
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
3
7 2 6 4 9 3 8 1 5
3 1 5 7 2 8 9 4 6
4 8 9 6 5 1 2 3 7
8 5 2 1 4 7 6 9 3
6 7 3 9 8 5 1 2 4
9 4 1 3 6 2 7 5 8
1 9 4 8 3 6 5 7 2
5 6 7 2 1 4 3 8 9
2 3 8 5 7 9 4 6 1
7 2 6 4 9 3 8 1 5
3 1 5 7 2 8 9 4 6
4 8 9 6 5 1 2 7 3
8 5 2 1 4 7 6 9 3
6 7 3 9 8 5 1 2 4
9 4 1 3 6 2 7 5 8
1 9 4 8 3 6 5 7 2
5 6 7 2 1 4 3 8 9
2 3 8 5 7 9 4 6 1
9 3 1 4 7 6 5 2 8
4 8 6 1 2 5 7 3 9
7 2 5 8 9 3 1 4 6
5 7 4 2 3 9 8 6 1
1 6 8 7 5 4 2 9 3
3 9 2 6 1 8 4 5 7
2 4 3 9 8 7 6 1 5
8 1 9 5 6 2 3 7 4
6 5 7 3 4 1 9 8 2

接下来,本文给出具体实现。实现中,通过替换 std::cin 的缓冲区,可在定义 DEBUG_ 宏的情况下从测试文件中读取内容。其他逻辑,可于上文参考。

validate_sudoku.cc
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
#include <iostream>
#include <cmath>
#include <cstdint>
#ifdef DEBUG_
#include <fstream>
namespace std {
ifstream fin{"./sudoku.test.txt"};
streambuf* cin_buf = cin.rdbuf(fin.rdbuf());
} // namespace std
#endif

class Sudoku {
private:
const size_t size_ = 9;
const size_t total_ = size_ * size_;
const size_t block_size_ = static_cast<const size_t>(std::sqrt(size_));
const int64_t flag_ = 0x1FF;
int* matrix_ = nullptr;

public:
Sudoku() : Sudoku(9) {}
explicit Sudoku(size_t size) :
size_{size},
total_{size_ * size_},
block_size_{CalculateBlockSize(size_)},
flag_{CalculateFlag(size_)},
matrix_{ConstructMatrix(size_)} {}
~Sudoku() {
DestroyMatrix(matrix_);
}

private:
Sudoku(const Sudoku&) = delete;
Sudoku(Sudoku&&) = delete;
Sudoku& operator=(const Sudoku&) = delete;
Sudoku& operator=(Sudoku&&) = delete;

private:
const size_t CalculateBlockSize(const size_t range) {
const size_t res = static_cast<const size_t>(std::sqrt(range));
if (not(range == res * res)) {
std::terminate();
}
return res;
}
const int64_t CalculateFlag(const size_t range) {
if (not(range <= 64)) {
std::terminate();
}
int64_t res = 0;
for (size_t i = 0; i != range; ++i) {
res |= 1 << i;
}
return res;
}
int* ConstructMatrix(const size_t total) {
return new int[total];
}
void DestroyMatrix(int*& matrix) noexcept {
if (nullptr != matrix) {
delete[] matrix;
matrix = nullptr;
}
return;
}

public:
bool ReadFromStream(std::istream& is) {
int* const m = const_cast<int* const>(this->matrix_);
if (is and m) {
for (size_t i = 0; i != total_; ++i) {
if (is) {
is >> m[i];
} else {
return false;
}
}
return true;
} else {
return false;
}
}
bool Validate() const {
const int* const m = const_cast<const int* const>(this->matrix_);
for (size_t i = 0; i != size_; ++i) { // validate rows
int64_t flag = 0x0;
for (size_t j = 0; j != size_; ++j) {
flag |= (1 << (m[i * size_ + j] - 1));
}
if (flag_ != flag) {
return false;
}
}
for (size_t j = 0; j != size_; ++j) { // validate columns
int64_t flag = 0x0;
for (size_t i = 0; i != size_; ++i) {
flag |= (1 << (m[i * size_ + j] - 1));
}
if (flag_ != flag) {
return false;
}
}
for (size_t i = 0; i != block_size_; ++i) { // validate blocks
for (size_t j = 0; j != block_size_; ++j) {
int64_t flag = 0x0;
for (size_t ii = 0; ii != block_size_; ++ii) {
for (size_t jj = 0; jj != block_size_; ++jj) {
flag |= (1 << (m[(i * block_size_ + ii) * size_ + j * block_size_ + jj] - 1));
}
}
if (flag_ != flag) {
return false;
}
}
}
return true;
}
};

int main() {
size_t case_num;
std::cin >> case_num;
Sudoku sudoku(9);
for (size_t i = 0; i != case_num; ++i) {
if (sudoku.ReadFromStream(std::cin)) {
std::cout << ((sudoku.Validate()) ? "YES" : "NO") << '\n';
}
}
return 0;
}

您的鼓励是我写作最大的动力

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。


撰写评论

写了这么多年博客,收到的优秀评论少之又少。在这个属于 SNS 的时代也并不缺少向作者反馈的渠道。因此,如果你希望撰写评论,请发邮件至我的邮箱并注明文章标题,我会挑选对读者有价值的评论附加到文章末尾。