猜數字很適合交給電腦來解。想法非常簡單,就是「把答案的候選全部寫出來,再把與提示矛盾的一個個刪掉」。

想法

  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 和 B。因為符號各不相同,所以可以這樣算:「位置對就是 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. 兩者都沒有的話,就揭開答案的其中一位。

(「提示」的用法)

想自己做遊戲的人,也請看看猜數字遊戲的做法。