Solucionador de Bulls and Cows

Bulls and Cows (o Cows & Bulls, o Pigs and Cows) es un juego de lógica basado en la deducción en el que el jugador debe adivinar un código secreto con el mínimo de intentos. El juego normalmente se juega entre dos jugadores con roles distintos: uno elige un código secreto (compuesto por números, letras o símbolos) y el otro intenta adivinarlo. Después de cada intento, se proporciona una respuesta en forma de « bulls » y « cows »: los bulls indican símbolos correctos en la posición correcta, mientras que los cows indican símbolos correctos en una posición incorrecta. El juego termina cuando se descubre completamente el código secreto.

El solucionador de Bulls and Cows se puede configurar según la longitud del código (número de posiciones) y el número de símbolos posibles, dependiendo del juego a resolver.

La sintaxis es CCCC A B donde CCCC es un intento, A es el número de « bulls » (símbolos correctos en la posición correcta) y B es el número de « cows » (símbolos correctos en posición incorrecta).

En la versión clásica, el código tiene 4 posiciones y utiliza dígitos (0–9), pero se puede usar cualquier combinación de letras, números o símbolos.

Para un código de tamaño N, cada intento debe contener N caracteres seguidos de 2 números que indiquen el resultado (bulls y cows). Separe cada intento con una nueva línea.

También es posible usar comodines (posiciones desconocidas indicadas con ?, *, - o _) tanto en los intentos como en los resultados.

Según Donald Knuth, en una configuración equivalente (código de 4 posiciones con 6 símbolos posibles), es posible encontrar el código en 5 intentos o menos. El algoritmo es el siguiente:

1 - Generar el conjunto E de todos los códigos posibles.

2 - Usar 1122 (o un equivalente) como primer intento.

3 - Si es correcto, el juego termina. Si no, eliminar de E todos los códigos incompatibles con la respuesta (bulls y cows).

4 - Para cada código restante no probado, calcular cuántas posibilidades de E se eliminarían para cada posible respuesta. Asignar una puntuación basada en el peor caso (mínimo de eliminaciones). Elegir un código que maximice esta puntuación, preferiblemente de E. Repetir desde el paso 3.

Este algoritmo permite encontrar el código en 5 intentos o menos.

Matemáticamente, si se conoce la estrategia del jugador, algunas combinaciones pueden ser más difíciles que otras. Sin embargo, con una estrategia óptima (como la de Knuth), todas se pueden resolver en 5 pasos o menos.

Si la estrategia no es conocida, ninguna combinación es intrínsecamente más difícil.

En la práctica, algunos patrones son más difíciles para los humanos:

— Los símbolos repetidos suelen pasarse por alto.

— Los símbolos poco comunes (números altos, letras raras) se prueban más tarde.

— Los patrones poco intuitivos (ej.: 1221, 5656) son más difíciles de anticipar.

Algunas combinaciones consideradas difíciles incluyen: 1221, 2354, 3311, 4524, 5656, 6643.

Una variante muy conocida es el juego Mastermind, que utiliza colores en lugar de números o símbolos, generalmente con un tablero físico y fichas.

Otra variante consiste en usar palabras, lo que aumenta considerablemente el número de combinaciones posibles.

También es posible permitir posiciones vacías, si los jugadores están de acuerdo.

Bulls and Cows se utiliza a menudo como base para acertijos o minijuegos en aplicaciones y videojuegos.

Bulls and Cows es un juego antiguo cuyo origen exacto es desconocido. Se jugaba mucho antes de Mastermind, normalmente como un juego de números con papel y lápiz.