猜數字很適合交給電腦來解。想法非常簡單,就是「把答案的候選全部寫出來,再把與提示矛盾的一個個刪掉」。
想法
- 列出所有答案的候選(4 位數有 5040 種)。
- 從候選中挑一個來猜。
- 看出現的 A 和 B,逐一檢查每個候選:「如果這個候選是答案,會得到同樣的 A 和 B 嗎?」不會的就刪掉。
- 重複 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「猜數字」的「提示」,也是把與目前所有線索不矛盾的答案候選全部數出來,然後依下列順序給出一個提示:
- 如果有某一位在所有候選中都是同一個符號,就告訴你那一位。
- 如果有哪個符號不在任何候選裡,就告訴你那個符號。
- 兩者都沒有的話,就揭開答案的其中一位。
(「提示」的用法)
想自己做遊戲的人,也請看看猜數字遊戲的做法。
