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
- Crie todos os candidatos a resposta (com 4 dígitos, são 5040).
- Escolha um dos candidatos e use como palpite.
- 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.
- 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'); judgeconta 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”.allCodescria todas as sequências de dígitos diferentes.solverepete: 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:
- Se houver uma posição em que todos os candidatos têm o mesmo símbolo, ela mostra essa posição.
- Se houver um símbolo que não aparece em nenhum candidato, ela mostra esse símbolo.
- Se não houver nenhum dos dois, ela revela uma posição da resposta.
Se você quiser criar seu próprio jogo, veja também Como criar um jogo de adivinhar números.
