숫자야구(일본에서는 히트 앤 블로라고 불러요)는 컴퓨터에게 풀게 하기에 딱 좋은 퍼즐이에요. 생각은 아주 단순해요. 「정답 후보를 전부 적어 놓고, 단서와 맞지 않는 것을 지워 가는 것」이 전부예요.

생각하는 방법

  1. 정답 후보를 모두 만든다(4자리라면 5040가지).
  2. 후보 가운데 하나를 골라 추리한다.
  3. 나온 히트와 블로를 보고, 후보마다 「그 후보가 정답이라면 같은 히트와 블로가 나올까」를 확인한다. 그렇지 않은 후보는 지운다.
  4. 맞힐 때까지 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. 어느 후보에서나 같은 기호가 들어가는 자리가 있으면 그 자리를 알려 준다.
  2. 어느 후보에도 들어 있지 않은 기호가 있으면 그것을 알려 준다.
  3. 어느 쪽도 없으면 정답의 한 자리를 공개한다.

이 순서로 하나를 보여 줘요(힌트 사용법).

직접 게임을 만들어 보고 싶다면 숫자 맞히기 게임 만드는 법도 읽어 보세요.