前言
上篇文章的内容是猜数字（Bulls and Cows）游戏的提示如何生成，这篇文章考虑另一个问题：如何设计猜数字游戏策略，使得对任意目标数字，都可以用较少的次数猜到。
这篇文章考虑的情形比上篇文章简单，目标数字一定是没有重复数字的 4 位数。
猜数字游戏规则
猜数字（Bulls and Cows）游戏由两个人玩，一方出数字，一方猜数字。
出数字的人想一个没有重复数字的 4 位数（最高位可以是 0），称为目标数字，猜数字的人每次猜一个 4 位数，猜的数同样不能有重复数字。每次猜数字之后，出数字的人需要给出形式为 "xAyB" 的提示，其中 x 和 y 分别表示「公牛」和「奶牛」的数量，「公牛」表示数字和位置都正确，「奶牛」表示数字正确但位置错误。如果猜数字的人得到的提示是 "4A0B"，则猜到目标数字。
猜数字游戏通常有次数限制猜数字游戏设计，猜数字的人在规定次数内猜到目标数字为胜利，否则为失败。常用的次数限制为 10 次，得到提示 "4A0B" 的一次猜数字也计入次数。
思路分析
没有重复数字 4 位数的个数是 A(10, 4)= 5040。如果直接遍历所有可能的没有重复数字 4 位数，则最坏情况下需要猜 5040 次才能猜到目标数字，显然不是好的策略。
其实，每次猜数字之后，可以根据得到的提示知道哪些数字可能是目标数字，哪些数字不可能是目标数字，从而缩小猜数字的范围。例如，猜数字 1024 得到的提示是 "1A2B"，则 2048 可能是目标数字，4096 不可能是目标数字。
假设猜的数字是 guess，可能的目标数字是 candidate（下文称为「候选目标数字」），则一定满足以下两个条件。
猜的数字 guess 中的每个「公牛」数字对应的候选目标数字 candidate 中的相同位置的数字一定相同，猜的数字 guess 中的每个非「公牛」数字对应的候选目标数字 candidate 中的相同位置的数字一定不同，因此 guess 和 candidate 的相同位置的数字相同的个数一定等于「公牛」的数量。
猜的数字 guess 中的每个正确数字（包括「公牛」和「奶牛」）一定在候选目标数字 candidate 中出现，猜的数字 guess 中的每个错误数字（既不是「公牛」也不是「奶牛」）一定不在候选目标数字 candidate 中出现，因此 guess 和 candidate 的公共数字（不考虑位置是否相同）的个数一定等于正确数字的个数（即「公牛」和「奶牛」的数量之和）。
第 2 个条件同时包含「公牛」和「奶牛」的数量，根据第 1 个条件，可以将「公牛」的数量减去，因此第 2 个条件等价于 guess 和 candidate 的位置不同的公共数字的个数一定等于「奶牛」的数量。
由于同时满足上述两个条件的数字的数量是有限的，因此在每次猜数字之后，都可以排除大部分数字，留下小部分候选目标数字，从而减少猜数字的次数。
根据上述分析可知，在第一次猜数字之后，不同的提示对应的可能的目标数字的数量如下：
如果得到 "4A0B" 的提示，则已经猜到目标数字。
"3A1B" 的提示不可能出现，因为此时 4 个数字都是正确的数字猜数字游戏设计3D交通工具，在 3 个数字的位置正确的情况下，剩下的 1 个数字的位置也一定正确，不可能只有 1 个数字的位置错误。
对于任意目标数字，在第一次猜数字之后，都可以将候选目标数字的数量减少到不超过 1440 个程序开发，因此可以显著减少猜数字的次数。每次猜数字之后都可以得到一个候选目标数字的集合，下一次猜数字时在该集合中任选一个数字并继续缩小猜数字的范围，直到猜到目标数字。
根据上述策略，猜到目标数字最多需要 9 次，平均需要 5.5 次。
实现实现说明
实现包括三个类：Master、BullsAndCows 和 TestBullsAndCows。
Master 类的功能是交互，包含一个私有的目标数字 secret 和一个公共的方法 guess，从外部无法直接访问目标数字，只能通过调用方法得到提示。
BullsAndCows 类的功能是实现猜数字策略，包含一个公共的方法 guessSecret，该方法的参数是 Master 类的一个实例，通过和该实例交互猜到目标数字。
TestBullsAndCows 类的功能是测试，根据特定的没有重复数字的 4 位数创建 Master 类的实例并创建 BullsAndCows 类的实例进行测试。为了统计猜到目标数字的次数，测试时考虑所有的没有重复数字的 4 位数。
代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
class Master {
public static final int LENGTH = 4;
private String secret;
public Master(String secret) {
this.secret = secret;
}
public String guess(String number) {
int bulls = 0, cows = 0;
int[] digits = new int[10];
for (int i = 0; i < LENGTH; i++) {
int secretDigit = secret.charAt(i) - '0';
int guessDigit = number.charAt(i) - '0';
if (secretDigit == guessDigit) {
bulls++;
} else {
if (digits[secretDigit] < 0) {
cows++;
}
if (digits[guessDigit] > 0) {
cows++;
}
digits[secretDigit]++;
digits[guessDigit]--;
}
}
return String.format("%dA%dB", bulls, cows);
}
}
class BullsAndCows {
private static Set secretSet;
private int turns;
public BullsAndCows() {
if (secretSet == null) {
secretSet = new HashSet();
for (int i = 0; i < 10000; i++) {
String secret = String.format("d", i);
if (allDifferent(secret)) {
secretSet.add(secret);
}
}
}
turns = 0;
}
public String guessSecret(Master master) throws Exception {
Set possibleSet = new HashSet(secretSet);
int bulls = 0, cows = 0;
while (bulls < Master.LENGTH) {
Iterator iterator = possibleSet.iterator();
String number = iterator.next();
String hint = master.guess(number);
turns++;
bulls = hint.charAt(0) - '0';
cows = hint.charAt(2) - '0';
if (bulls == Master.LENGTH) {
return number;
}
iterator.remove();
while (iterator.hasNext()) {
String candidate = iterator.next();
if (!isPossible(number, candidate, bulls, cows)) {
iterator.remove();
}
}
}
throw new Exception("Secret not found!");
}
public int getTurns() {
return turns;
}
private static boolean allDifferent(String secret) {
boolean[] exists = new boolean[10];
for (int i = 0; i < Master.LENGTH; i++) {
int digit = secret.charAt(i) - '0';
if (exists[digit]) {
return false;
}
exists[digit] = true;
}
return true;
}
private static boolean isPossible(String guess, String candidate, int bulls, int cows) {
int actualBulls = 0;
int actualCows = 0;
boolean[] exists = new boolean[10];
for (int i = 0; i < Master.LENGTH; i++) {
int digit = guess.charAt(i) - '0';
exists[digit] = true;
}
for (int i = 0; i < Master.LENGTH; i++) {
if (candidate.charAt(i) == guess.charAt(i)) {
actualBulls++;
} else {
int digit = candidate.charAt(i) - '0';
if (exists[digit]) {
actualCows++;
}
}
}
if (bulls != actualBulls || cows != actualCows) {
return false;
}
return true;
}
}
public class TestBullsAndCows {
private static int maxTurns = 0;
private static int minTurns = Integer.MAX_VALUE;
private static int sumTurns = 0;
public static void main(String[] args) {
List secretList = new ArrayList();
for (int i = 0; i < 10000; i++) {
String secret = String.format("d", i);
if (allDifferent(secret)) {
secretList.add(secret);
}
}
int size = secretList.size();
for (int i = 0; i < size; i++) {
testGuess(secretList, i);
}
System.out.println("Maximum turns: " + maxTurns);
System.out.println("Minimum turns: " + minTurns);
double meanTurns = 1.0 * sumTurns / size;
System.out.println("Mean turns: " + meanTurns);
}
private static boolean allDifferent(String secret) {
boolean[] exists = new boolean[10];
for (int i = 0; i < Master.LENGTH; i++) {
int digit = secret.charAt(i) - '0';
if (exists[digit]) {
return false;
}
exists[digit] = true;
}
return true;
}
private static void testGuess(List secretList, int index) {
Master master = new Master(secretList.get(index));
BullsAndCows obj = new BullsAndCows();
try {
String secret = obj.guessSecret(master);
System.out.println("Expected secret: " + secretList.get(index));
System.out.println("Guessed secret: " + secret);
System.out.println("Used turns: " + obj.getTurns());
maxTurns = Math.max(maxTurns, obj.getTurns());
minTurns = Math.min(minTurns, obj.getTurns());
sumTurns += obj.getTurns();
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
}
} 结语
这篇文章使用的策略是简单策略，猜到目标数字最多需要 9 次，平均需要 5.5 次。除了简单策略以外，还有启发式策略和最优策略，在最多次数和平均次数方面都优于简单策略，感兴趣的读者可以自行尝试。
