O Hit & Blow é um quebra-cabeça ideal para o computador resolver. A ideia é bem simples: “escrever todos os candidatos a resposta e ir eliminando os que contradizem as pistas”.

A ideia

  1. Crie todos os candidatos a resposta (com 4 dígitos, são 5040).
  2. Escolha um dos candidatos e use como palpite.
  3. Olhe os certos e os quase que apareceram e verifique, para cada candidato: “se ele fosse a resposta, daria os mesmos certos e quase?“. Se não daria, elimine.
  4. Repita os passos 2 e 3 até acertar.

O ponto-chave é o passo 3, em que só ficam os candidatos que dariam a mesma pista. É o raciocínio que a gente faz de cabeça, feito de forma mecânica para todos os candidatos.

O programa

Em JavaScript, fica assim. Você pode rodar nas ferramentas de desenvolvedor do navegador ou com o Node.js no computador.

// Conta os certos e os quase
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];
}

// Cria todas as sequências de dígitos diferentes
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;
}

// Usa sempre o primeiro candidato que não contradiz as pistas
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 conta os certos e os quase a partir da resposta e do palpite. Como todos os símbolos são diferentes, dá para contar assim: “se está no lugar certo, é certo; se não está, mas aparece na resposta, é quase”.
  • allCodes cria todas as sequências de dígitos diferentes.
  • solve repete: usa o primeiro candidato como palpite e mantém só os candidatos que dariam a mesma pista.

Resultado da execução

Com a resposta “4719”, a saída foi esta (da esquerda para a direita: número da tentativa, palpite, certos, quase e quantidade de candidatos antes do palpite).

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

Os candidatos foram diminuindo, 5040 → 1440 → 369 → 80 → 15 → 6 → 1, e o acerto veio na 7ª tentativa. Fazendo esse programa resolver todas as 5040 respostas, a média foi de cerca de 5,56 tentativas, e a resposta mais demorada levou 9.

Como resolver com menos tentativas

Esse programa sempre usa o “primeiro candidato” como palpite. Escolher melhor o palpite reduz o número de tentativas.

  • Escolher o palpite que divide bem o que sobra: para cada palpite possível, conte como os candidatos se dividem pelas pistas que podem aparecer, e escolha o palpite em que o maior grupo restante seja o menor, ou em que a média do que sobra seja a menor.
  • Usar também sequências que não são candidatos: mesmo uma sequência que você já sabe que está errada pode compensar se dividir bem os candidatos.

Com essas ideias, em 4 dígitos qualquer resposta é resolvida em até 7 tentativas, com média de cerca de 5,3 (Existe uma estratégia infalível no Hit & Blow?). Em compensação, cada palpite exige examinar muitas combinações, então o cálculo demora mais.

A “Dica” do app segue a mesma ideia

A “Dica” do app “Adivinhe o Número” também conta todos os candidatos de resposta que não contradizem as pistas até agora e mostra uma coisa, nesta ordem:

  1. Se houver uma posição em que todos os candidatos têm o mesmo símbolo, ela mostra essa posição.
  2. Se houver um símbolo que não aparece em nenhum candidato, ela mostra esse símbolo.
  3. Se não houver nenhum dos dois, ela revela uma posição da resposta.

(Como usar a Dica)

Se você quiser criar seu próprio jogo, veja também Como criar um jogo de adivinhar números.