Solveur Bulls and Cows

Bulls and Cows (ou Cows & Bulls, ou Pigs and Cows) est un jeu de logique basé sur la déduction dans lequel le joueur doit deviner un code secret en un minimum de tentatives. Le jeu se joue généralement à 2 joueurs avec des rôles distincts : l'un choisit un code secret (composé de chiffres, lettres ou symboles), l'autre tente de le deviner. Après chaque proposition, le joueur reçoit un retour sous forme de « bulls » et « cows » : les bulls indiquent les éléments corrects et bien placés, tandis que les cows indiquent les éléments corrects mais mal placés. La partie se termine lorsque le code secret est entièrement trouvé.

Le solveur Bulls and Cows est paramétrable selon la taille du code (nombre de positions) et le nombre de symboles possibles, en fonction de la partie à résoudre.

La syntaxe à utiliser est CCCC A B où CCCC représente une proposition, A le nombre de « bulls » (symboles corrects bien placés) et B le nombre de « cows » (symboles corrects mal placés).

Dans la version classique, le code comporte 4 positions et utilise des chiffres (0-9), mais toute combinaison de lettres, chiffres ou symboles est possible.

Pour une combinaison de taille N, chaque proposition doit contenir N caractères suivis de 2 nombres indiquant les indices (bulls et cows). Chaque proposition doit être séparée par un retour à la ligne.

Il est possible d'utiliser des jokers (positions inconnues notées ?, *, - ou _) aussi bien dans la combinaison que dans les scores.

Selon Donald Knuth, dans une configuration équivalente (code de 4 positions avec 6 symboles possibles), il est possible de trouver le code en 5 tentatives ou moins. L'algorithme est le suivant :

1 - Générer l'ensemble E de tous les codes possibles.

2 - Proposer 1122 (ou un équivalent) comme première tentative.

3 - Si la réponse est correcte, la partie s'arrête. Sinon, éliminer de E tous les codes incompatibles avec le résultat (bulls et cows).

4 - Pour chaque code non encore testé, calculer combien d'éléments de E seraient éliminés pour chaque réponse possible. Attribuer un score correspondant au pire cas (minimum d'éléments éliminés). Choisir un code maximisant ce score, de préférence appartenant à E. Revenir à l'étape 3.

Cet algorithme garantit de trouver le code en 5 tentatives ou moins.

Mathématiquement, si la stratégie du joueur est connue, certaines combinaisons peuvent être plus difficiles que d'autres. Cependant, avec une stratégie optimale (comme celle de Knuth), toutes les combinaisons sont trouvables en 5 étapes ou moins.

Si la stratégie n'est pas connue, aucune combinaison n'est intrinsèquement plus difficile qu'une autre.

Dans la pratique, certaines combinaisons peuvent piéger les joueurs humains :

— Les doublons (symboles répétés) sont souvent négligés.

— Les symboles inhabituels (chiffres élevés, lettres rares) sont testés plus tard.

— Des motifs peu intuitifs (ex : 1221, 5656) sont plus difficiles à anticiper.

Certaines combinaisons réputées difficiles incluent : 1221, 2354, 3311, 4524, 5656, 6643.

Une variante bien connue est le jeu Mastermind, qui utilise des couleurs à la place de chiffres ou symboles, avec un support physique (plateau et pions).

Une autre variante consiste à utiliser des mots à deviner, ce qui augmente fortement le nombre de combinaisons possibles.

Il est également possible d'autoriser des positions vides (cases sans symbole), si les joueurs sont d'accord.

Bulls and Cows est souvent utilisé comme base pour des énigmes ou mini-jeux dans des applications et jeux vidéo.

Bulls and Cows est un jeu ancien dont l'origine exacte est inconnue. Il était déjà joué bien avant la création du Mastermind, notamment sous forme de jeu de chiffres ou de papier-crayon.