숫자야구(일본에서는 히트 앤 블로라고 불러요)는 컴퓨터에게 풀게 하기에 딱 좋은 퍼즐이에요. 생각은 아주 단순해요. 「정답 후보를 전부 적어 놓고, 단서와 맞지 않는 것을 지워 가는 것」이 전부예요.
생각하는 방법
- 정답 후보를 모두 만든다(4자리라면 5040가지).
- 후보 가운데 하나를 골라 추리한다.
- 나온 히트와 블로를 보고, 후보마다 「그 후보가 정답이라면 같은 히트와 블로가 나올까」를 확인한다. 그렇지 않은 후보는 지운다.
- 맞힐 때까지 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번이 되었어요(히트 앤 블로에 필승법이 있을까?). 대신 추리를 하나 고를 때마다 아주 많은 조합을 살펴봐야 해서 계산에 시간이 걸려요.
앱의 「힌트」도 같은 생각
앱 「숫자야구」의 「힌트」도 지금까지의 단서와 맞는 정답 후보를 모두 세어서,
- 어느 후보에서나 같은 기호가 들어가는 자리가 있으면 그 자리를 알려 준다.
- 어느 후보에도 들어 있지 않은 기호가 있으면 그것을 알려 준다.
- 어느 쪽도 없으면 정답의 한 자리를 공개한다.
이 순서로 하나를 보여 줘요(힌트 사용법).
직접 게임을 만들어 보고 싶다면 숫자 맞히기 게임 만드는 법도 읽어 보세요.
