ヒット&ブローは、コンピューターに解かせるのにちょうどいいパズルです。考え方はとても単純で、「答えの候補を全部書き出して、手がかりと矛盾するものを消していく」だけです。
考え方
- 答えの候補を全部作る(4桁なら5040通り)。
- 候補の中から1つ選んで予想する。
- 出たヒットとブローを見て、「もしその候補が答えだったら、同じヒットとブローになるか」を、候補ごとに確かめる。ならないものは消す。
- 当たるまで2と3をくり返す。
3の「同じ手がかりになる候補だけを残す」がポイントです。人が頭の中でしている推理を、全部の候補について機械的に行います。
プログラム
JavaScriptで書くと、次のようになります。ブラウザの開発者ツールや、パソコンのNode.jsで動かせます。
// ヒットとブローを数える
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は、答えと予想から、ヒットとブローを数えます。記号がすべてちがうので、「場所が合えばヒット、合わなくても答えに入っていればブロー」と数えられます。allCodesは、すべてちがう数字の並びを全部作ります。solveは、候補の先頭を予想し、同じ手がかりになる候補だけを残す、をくり返します。
実行結果
答えが「4719」のとき、表示は次のようになりました(左から、何回目・予想・ヒット・ブロー・予想する前の候補の数)。
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回になりました(ヒット&ブローの必勝法はある?)。そのかわり、予想を1つ選ぶたびに、たくさんの組み合わせを調べるので、計算に時間がかかります。
アプリの「ひらめき」も同じ考え方
アプリ「ヒット&ブロー」の「ひらめき」も、今までの手がかりと矛盾しない答えの候補を全部数えて、
- どの候補でも同じ記号になる桁があれば、その桁を教える。
- どの候補にも入っていない記号があれば、それを教える。
- どちらもなければ、答えの桁を1つ明かす。
の順に1つ示しています(ひらめきの使い方)。
自分でゲームを作ってみたい人は、数当てゲームの作り方も見てください。
