最近一个朋友在用计算机模拟人来玩文曲星上的
“猜数字”游戏，也邀我一起讨论。我以前没有玩过，不过发现这个还是蛮有趣的，于是也想写一个能猜数据的小程序。
通过几日思考，终于实现了一个稍微有点聪明的。以下是C++代码（
下载源代码）。
首先函数头的定义部分，其中一个重要的数据结构是各个排列之间的关系矩阵。
我们使用 char 来表示两个排列的关系，char值的计算方法为“A*10+B”；譬如假设 排列i 与 排列j 的关系为“1A2B”，则 table[i][j] = (char)12。
1 #include <iostream>
2
3 #define N 4 // 排列长度
4 #define M (10*9*8*7) // 总的可能排列数
5 #define MATCH (N*10) // 猜测正确时的judge()返回值
6
7 #define swap(a,b) {int t=a; a=b; b=t;}
8
9 int arrange[M][N]; // 所有可能排列的列表，一行一个排列
10 char table[M][M]; // 各排列之间的关系矩阵
11
12 int arr_count; // 用于生成所有排列时使用的全局变量
判断两个排列之间关系的函数：
1 // 判断两个排列之间的关系
2 // 譬如如果结果为“1A2B”，则返回值为 (char)12
3 char judge(int v1[], int v2[])
4 {
5 int a = 0;
6 int b = 0;
7 for (int i=0; i<N; i++) {
8 if( v1[i] == v2[i])
9 a += 1;
10 for (int j=0; j<N; j++) {
11 if (v1[i] == v2[j])
12 b += 1;
13 }
14 }
15 b -= a;
16 return (char)(a * 10 + b);
17 }
18
初始化排列列表：
1 // 使用递归方法计算排列
2 void arr(int a[], int start)
3 {
4 if (start == N) {
5 for (int i=0; i<N; i++)
6 arrange[arr_count][i] = a[i];
7 arr_count++;
8 return;
9 }
10 for (int i=start; i<=9; i++) {
11 swap(a[start], a[i]);
12 arr(a, start+1);
13 swap(a[start], a[i]);
14 }
15 }
16
17 // 初始化所有可能排列情况的列表
18 void init_arrange()
19 {
20 int a[10];
21 arr_count = 0;
22 for (int i=0; i<=9; i++)
23 a[i] = i;
24 arr(a, 0);
25 }
初始化关系矩阵：
1 // 初始化各个排列间的关系矩阵
2 void init_table()
3 {
4 for (int i=0; i<M; i++) {
5 for (int j=0; j<=i; j++) {
6 table[i][j] = table[j][i] = judge(arrange[i], arrange[j]);
7 }
8 }
9 }
为了方便，这里有一些打印信息的函数：
1 // 按照“[0 1 2 3]”的形式打印排列
2 void print_arrange(int arr_index)
3 {
4 std::cout << "[";
5 for (int i=0; i<N; i++) {
6 if (i != 0)
7 std::cout << " ";
8 std::cout << arrange[arr_index][i];
9 }
10 std::cout << "]";
11 }
12
13 // 按照类似“0A0B”的形式打印裁判的结果
14 void print_result(char result)
15 {
16 std::cout << ((int)result/10) << "A" << ((int)result%10) << "B" <<std::endl;
17 }
18
19 // 打印一次猜测与结果的信息
20 void print_guess_info(int arr_index, char result) {
21 print_arrange(arr_index);
22 std::cout << " --> ";
23 print_result(result);
24 std::cout << std::endl;
25 }
便于扩展，使用抽象类。以下是裁判与玩家双方的接口：
1 // 玩家的抽象类
2 class Player
3 {
4 public:
5 // 开始游戏前的初始化
6 virtual void init() = 0;
7 // 获取下一次猜测的排列
8 virtual int getNextGuess() = 0;
9 // 告诉玩家上一次猜测的结果
10 virtual void setGuessResult(int arr_index, char result) = 0;
11 };
12
13 // 裁判的抽象类
14 class Judgment
15 {
16 public:
17 // 开始游戏前的初始化
18 virtual void init() = 0;
19 // 对猜测进行判断，返回结果
20 virtual char doJudge(int arr_index) = 0;
21 };
现在让玩家玩一次游戏，直到猜成功：
1 // 玩一次游戏，返回猜测次数
2 int play(Player * p, Judgment * j) {
3 int time = 0;
4 p->init();
5 j->init();
6 while (1) {
7 int guess = p->getNextGuess();
8 char result = j->doJudge(guess);
9 // print_guess_info(guess, result);
10 time++;
11 if (result == (char)MATCH)
12 break;
13 p->setGuessResult(guess, result);
14 }
15 return time;
16 }
寻找一个诚实的裁判：
1 class HonestJudgment
2 : public Judgment
3 {
4 int _my_arr[N];
5 public:
6 HonestJudgment() { }
7 ~HonestJudgment() { }
8 public:
9 void init() { }
10 // 设置裁判的正确结果
11 void setArrange(int arr[]) {
12 for (int i=0; i<N; i++)
13 _my_arr[i] = arr[i];
14 }
15 // 这是一个诚实的裁判，所以会诚实地裁决
16 char doJudge(int arr_index) {
17 return judge(_my_arr, arrange[arr_index]);
18 }
19 };
有了裁判，还要找一个玩家。我们先找一个头脑简单点的玩家：
1 class NaivePlayer
2 : public Player
3 {
4 bool _cand[M];
5 int _cand_count;
6 public:
7 NaivePlayer() { }
8 ~NaivePlayer() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜测总是使用第一个排列
17 if (_cand_count == M)
18 return 0;
19 // 返回遇到的第一个可行排列
20 for (int i=0; i<M; i++) {
21 if (_cand[i]) {
22 return i;
23 }
24 }
25 }
26 void setGuessResult(int arr_index, char result) {
27 // 依据返回结果进一步排除已有的可行排列
28 for (int j=0; j<M; j++) {
29 if (_cand[j] && table[arr_index][j] != result)
30 _cand[j] = false;
31 _cand_count--;
32 }
33 }
34 };
用Factory工厂制造裁判和玩家（哈哈，批量生产）：
1 Player * player_factory()
2 {
3 return new NaivePlayer();
4 }
5
6 Judgment * judgment_factory()
7 {
8 return new HonestJudgment();
9 }
现在让大家玩起来吧：
1 int main()
2 {
3 int time_stat[M]; // 次数统计表
4 Judgment *jp;
5 Player *pp;
6 // 获取实例
7 jp = judgment_factory();
8 pp = player_factory();
9 // 初始化次数统计表
10 for (int i=0; i<M; i++)
11 time_stat[i] = 0;
12 // 初始化排列列表和关系矩阵
13 init_arrange();
14 init_table();
15 // 每一种排列情况都玩一次
16 for (int i=0; i<M; i++) {
17 ((HonestJudgment*)jp)->setArrange(arrange[i]);
18 int t = play(pp, jp);
19 print_arrange(i);
20 std::cout << " : " << t << std::endl;
21 time_stat[t]++;
22 }
23 // 统计结果
24 int total = 0;
25 std::cout << "-------------" << std::endl;
26 for (int i=0; i<M; i++) {
27 if (time_stat[i]) {
28 std::cout << i << "\t" << time_stat[i] << std::endl;
29 total += time_stat[i]*i;
30 }
31 }
32 std::cout << "Average: " << total << "/" << M << " = " << (float)total/M << std::endl;
33 std::cout << "-------------" << std::endl;
34 delete jp;
35 delete pp;
36 return 0;
37 }
得到的统计数据：
NaivePlayer Algorithm:
-------------
1 1
2 13
3 108
4 596
5 1664
6 1770
7 755
8 128
9 5
Average: 28029/5040 = 5.56131
-------------
虽然头脑简单，但是还都能猜出来，只是次数多了点。
好了，现在整个框架搭起来了。现在的任务是寻找更聪明的玩家，让猜测次数降下来。
还真找到了一个贪婪的玩家（算法原理见代码注释），且叫他 Clever1Player 吧：
1 class Clever1Player
2 : public Player
3 {
4 bool _cand[M]; // 排列是否可行的标志矩阵
5 int _cand_count; // 当前可行排列的个数
6 public:
7 Clever1Player() { }
8 ~Clever1Player() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜测总是使用第一个排列
17 if (_cand_count == M)
18 return 0;
19 // 当只有一个可行排列时，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 悲观假设：
27 // 假设无论猜什么排列，电脑总是能聪明地返回结果，
28 // 使得依据返回结果能进一步排除掉的可行排列数目最少（即剩余的可行排列数目最多）
29 // 贪婪算法：
30 // 从可行排列中选择下一次猜测的排列；
31 // 在悲观假设总是成立的条件下，使得每次排除掉的可行排列数目最多（即剩余的可行排列数目最少），即求最好的最坏情况；
32 ///////////////////
33 int res_count[MATCH+1];
34 int min_max = M+1;
35 int min_max_index;
36 for (int i=0; i<M; i++) {
37 // 对于每一个可行排列 Ri
38 if (_cand[i]) {
39 // 下一次猜测排列 Ri 的时候，裁判将会返回一个结果；
40 // 根据悲观假设，裁判返回的结果总是使得依据返回结果能进一步排除掉的可行排列数目最少（即剩余的可行排列数目最多）
41 // cur_max 记录该最坏情况下剩余的可行排列的数目
42 int cur_max = 0;
43 for (int j=0; j<=MATCH; j++)
44 res_count[j] = 0;
45 for (int j=0; j<M; j++) {
46 if (_cand[j])
47 res_count[ (int)table[i][j] ]++;
48 }
49 for (int j=0; j<=MATCH; j++)
50 if (res_count[j] > cur_max)
51 cur_max = res_count[j];
52 // 如果 cur_max 小于全局 min_max，则更新 min_max，并记录下当前排列的序号
53 // 这样能找到最好最坏情况
54 if (cur_max < min_max) {
55 min_max = cur_max;
56 min_max_index = i;
57 }
58 }
59 }
60 // 返回最好最坏情况下的排列序号
61 return min_max_index;
62 }
63 void setGuessResult(int arr_index, char result) {
64 // 依据返回结果进一步排除已有的可行排列
65 for (int j=0; j<M; j++) {
66 if (_cand[j] && table[arr_index][j] != result) {
67 _cand[j] = false;
68 _cand_count--;
69 }
70 }
71 }
72 };
73
74 // 让工厂开始生产我
75 Player * player_factory()
76 {
77 return new Clever1Player();
78 }
好了，Clever1Player 也来玩了，看看他的成绩：
Clever1Player Algorithm:
-------------
1 1
2 13
3 108
4 620
5 2002
6 1937
7 356
8 3
Average: 26979/5040 = 5.35298
-------------
成绩还不错，不过最差情况下要猜8次嘛。
有人说最多7次就可以猜出来，我们再找找。
没想到 Clever1Player 的兄弟 Clever2Player 也会玩，而且玩的也不错（算法原理见代码注释）：
1 class Clever2Player
2 : public Player
3 {
4 bool _cand[M];
5 int _cand_count;
6 public:
7 Clever2Player() { }
8 ~Clever2Player() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜测总是使用第一个排列
17 if (_cand_count == M)
18 return 0;
19 // 当只有一个可行排列时，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 与Clever1Player的区别：
27 // 下一次猜测的排列不局限于可行排列
28 ///////////////////
29 int res_count[MATCH+1];
30 int min_max = M+1;
31 int min_max_index;
32 for (int i=0; i<M; i++) {
33 // 对于所有排列 Ri
34 int cur_max = 0;
35 for (int j=0; j<=MATCH; j++)
36 res_count[j] = 0;
37 for (int j=0; j<M; j++) {
38 if (_cand[j])
39 res_count[ (int)table[i][j] ]++;
40 }
41 for (int j=0; j<=MATCH; j++)
42 if (res_count[j] > cur_max)
43 cur_max = res_count[j];
44 if (cur_max < min_max) {
45 min_max = cur_max;
46 min_max_index = i;
47 }
48 }
49 return min_max_index;
50 }
51 void setGuessResult(int arr_index, char result) {
52 for (int j=0; j<M; j++) {
53 if (_cand[j] && table[arr_index][j] != result) {
54 _cand[j] = false;
55 _cand_count--;
56 }
57 }
58 }
59 };
60
61 // 让工厂开始生产我
62 Player * player_factory()
63 {
64 return new Clever2Player();
65 }
Clever2Player 的成绩：
Clever2Player Algorithm:
-------------
1 1
2 2
3 22
4 176
5 1301
6 2885
7 653
Average: 29161/5040 = 5.78591
-------------
不错，果然在7次之内都能猜出来。只是为什么平均成绩还不如 Clever1Player 呢？
这个问题，我得找时间问问他。
当前Clever1Player时间复杂度为 (M*M*Time) ，其中Time为猜测次数。考虑次数总小于10，所以时间复杂度为 (M^2)。
我曾经做过优化，即使用一个数组保存可行排列序号，这样在 Clever1Player 的 36 和 45 行就只需要扫描数组，而不需要每次都扫描 M 次了。当然总的时间复杂度依然是 (M^2)。
Clever2Player 与 Clever1Player 的唯一区别在于 “去掉了Clever1Player 的第 38 行”，使得“下一次猜测的排列不局限于可行排列”。
基于的考虑是：
-------------
假设正确结果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下来不能猜 4567 ，因为 4567 不在可行集中（已经排除）。
但是Clever2Player 则有可能会猜 4567 得到 0A1B，直观上说，猜测范围就缩小到 01234567 中了，搜索空间减小很多。实际上我们人脑使用逻辑推理的时候通常就是这么考虑的，而且我们肯定是不会使用这种搜索算法的。
至于逻辑推理法与搜索法之间有什么联系，我也不清楚。
-------------
另外，该算法的关注点在于猜测次数，即在于效果而不是效率。所以为了使算法看起来清晰，我没有过多优化。
NaivePlayer 算法执行时间最快，大约1分钟跑完所有5040种情况，Clever1Player大约5分钟，Clever2Player大约10分钟。
另外我也曾考虑过“动态规划”算法，递推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是当前可行集，t(F) 为该可行集 F 条件下猜出结果的次数，f 为 F 中的一个可行排列。
但是我没有编程实现，因为担心复杂度太高运行不完。
而贪心算法得到的应当不是最优解，但是近似最优解，而且从次数和执行效率上来说都是可以接受的。
下一步做什么呢？
我们可以找一个狡猾的裁判，他让玩家 Clever1Player 和 Clever1Player 的“悲观假设”变成现实。
一边是聪明的玩家，一边是狡猾的裁判，哈哈，有好戏看了。
究竟鹿死谁手，请听下回分解。
最后感谢
东坡_居士，让我有机会接触这么好玩的游戏。