猜数字很适合拿来让电脑解。思路非常简单:“把答案的候选全部写出来,再把与提示矛盾的一个个划掉”,仅此而已。人在脑子里做的推理,电脑对所有候选机械地做一遍。

思路

  1. 列出答案的所有候选(4位的话有5040种)。
  2. 从候选中选一个来猜。
  3. 看出现的A和B,对每个候选确认:“如果它是答案,会不会得到同样的A和B?”不会的就划掉。
  4. 重复2和3,直到猜中。

关键在第3步的“只留下提示相同的候选”。

程序

用 JavaScript 写出来是下面这样。可以在浏览器的开发者工具里,或者在电脑的 Node.js 上运行。

// 数出A和B的个数
function judge(answer, guess) {
  let hit = 0, blow = 0;
  for (let i = 0; i < guess.length; i++) {
    if (guess[i] === answer[i]) hit++;
    else if (answer.includes(guess[i])) blow++;
  }
  return [hit, blow];
}

// 列出所有各不相同的数字排列
function allCodes(digits, prefix = '') {
  if (prefix.length === digits) return [prefix];
  const list = [];
  for (const d of '0123456789') {
    if (!prefix.includes(d)) list.push(...allCodes(digits, prefix + d));
  }
  return list;
}

// 一直猜与提示不矛盾的候选中的第一个
function solve(answer) {
  let candidates = allCodes(answer.length);
  for (let turn = 1; ; turn++) {
    const guess = candidates[0];
    const [hit, blow] = judge(answer, guess);
    console.log(turn, guess, hit, blow, candidates.length);
    if (hit === answer.length) return turn;
    candidates = candidates.filter((c) => {
      const [h, b] = judge(c, guess);
      return h === hit && b === blow;
    });
  }
}

solve('4719');
  • judge 根据答案和猜测,数出A(hit)和B(blow)的个数。因为符号各不相同,所以可以这样数:“位置对就算A,位置不对但在答案里就算B”。
  • allCodes 把符号各不相同的数字排列全部列出来。
  • solve 不断重复:猜候选中的第一个,只留下提示相同的候选。

运行结果

答案是“4719”时,输出如下(从左到右依次是:第几次、猜测、A、B、猜之前的候选数)。

1 0123 0 1 5040
2 1456 0 2 1440
3 2547 0 2 369
4 3674 0 2 80
5 4268 1 0 15
6 4395 1 1 6
7 4719 4 0 1

候选数从 5040 → 1440 → 369 → 80 → 15 → 6 → 1 一路减少,第7次猜中。让这个程序把5040种答案全部解一遍,平均约5.56次,最慢的答案用了9次。

想用更少的次数解出来

这个程序总是猜“候选中的第一个”。如果在选猜测的方式上下点功夫,就能减少次数。

  • 选能把剩余候选分得好的猜测:对每个可选的猜测,数一数可能出现的各种提示会把答案候选分成怎样的几组,然后选“剩得最多的那一组最小”的猜测,或者“剩余候选的平均数最小”的猜测。
  • 也用不在候选里的排列来猜:即使已知不可能是答案,只要能把候选分得好,有时反而划算。

用了这些窍门,4位时不管答案是什么都能在7次以内猜中,平均约5.3次(猜数字有必胜法吗?)。代价是每选一个猜测都要检查大量组合,所以计算要花时间。

App 的“提示”也是同样的思路

App“猜数字”的“提示”,也是先数出与目前所有提示都不矛盾的答案候选,然后

  1. 如果有某一位在所有候选里都是同一个符号,就告诉你这一位。
  2. 如果有某个符号没有出现在任何候选里,就告诉你这个符号。
  3. 两者都没有的话,就揭开答案的一位。

按这个顺序给出一条(“提示”的用法)。

想自己做游戏的人,也请看看猜数字游戏的做法。