Hit & Blow (le nom au Japon de Bulls and Cows) est un puzzle idéal pour un ordinateur. L’idée est très simple : écrire toutes les réponses possibles, puis barrer celles qui contredisent les indices.
L’idée
- Fabriquer toutes les réponses possibles (5040 pour 4 chiffres).
- Choisir un candidat et le proposer.
- Regarder les « bien placés » (hits) et les « mal placés » (blows) obtenus. Pour chaque candidat, vérifier : « Si c’était la réponse, obtiendrait-on les mêmes hits et blows ? » Barrer ceux qui ne donnent pas le même résultat.
- Répéter les étapes 2 et 3 jusqu’à trouver.
Tout est dans l’étape 3 : ne garder que les candidats qui donneraient le même indice. C’est le raisonnement qu’une personne fait dans sa tête, appliqué mécaniquement à chaque candidat.
Le programme
En JavaScript, cela donne ceci. Vous pouvez l’exécuter dans les outils de développement de votre navigateur ou avec Node.js sur un ordinateur.
// Compter les hits et les blows
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];
}
// Fabriquer toutes les suites de chiffres tous différents
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;
}
// Proposer toujours le premier candidat compatible avec les indices
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'); judgecompte les hits et les blows à partir de la réponse et de l’essai. Comme tous les symboles sont différents, on compte ainsi : « bonne place : hit ; sinon, présent dans la réponse : blow ».allCodesfabrique toutes les suites de chiffres tous différents.solvepropose le premier candidat, puis ne garde que les candidats qui donneraient le même indice, et recommence.
Le résultat
Quand la réponse est « 4719 », voici ce qui s’affiche (de gauche à droite : numéro de l’essai, essai, hits, blows, nombre de candidats avant l’essai).
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 Les candidats passent de 5040 à 1440, 369, 80, 15, 6, puis 1, et la réponse est trouvée au 7e essai. Si ce programme résout les 5040 réponses possibles une par une, il lui faut environ 5,56 essais en moyenne, et 9 essais pour la réponse la plus difficile.
Comment gagner des essais
Ce programme propose toujours le « premier candidat ». En choisissant mieux ses essais, on peut réduire le nombre de coups.
- Choisir l’essai qui répartit le mieux ce qui reste : pour chaque essai possible, compter comment les candidats se répartissent selon les indices possibles, et choisir l’essai dont le plus gros groupe est le plus petit, ou celui dont le reste moyen est le plus petit.
- Utiliser aussi des suites qui ne sont pas candidates : même une suite que l’on sait fausse peut être rentable si elle répartit bien les candidats.
Avec ces idées, à 4 chiffres, toutes les réponses se trouvent en 7 essais au plus, avec une moyenne d’environ 5,3 essais (Existe-t-il une stratégie gagnante à Hit & Blow ?). En contrepartie, chaque choix d’essai oblige à examiner beaucoup de combinaisons, donc le calcul prend du temps.
L’« Indice » de l’appli suit la même idée
L’« Indice » de l’appli « Devine le Nombre » compte lui aussi toutes les réponses encore compatibles avec les indices obtenus, puis montre une seule chose, dans cet ordre :
- S’il y a une case où tous les candidats ont le même symbole, il vous dit laquelle.
- S’il y a un symbole présent dans aucun candidat, il vous le dit.
- Sinon, il révèle une case de la réponse.
Si vous voulez créer votre propre jeu, lisez aussi Comment créer un jeu de devinettes de chiffres.
