Muertos y Heridos: un juego de lógica (I)

Descripción del juego

Muertos y Heridos es un juego de lógica para el que solo se necesita lápiz y papel. Se juega entre dos jugadores, el cifrador que piensa un número de 4 cifras del 0 al 9999, la clave, y el descifrador que trata de deducirlo.
En cada intento el descifrador pregunta un número de cuatro cifras. El cifrador responde con un número de dos cifras. La primera, los muertos, representa el número de dígitos de la pregunta que coinciden con alguno de la clave y además se encuentran en la misma posición. La segunda, los heridos, representa el número de dígitos de la pregunta que coinciden con alguno de la clave pero que no están en la misma posición. Se muestran a continuación dos ejemplos. La clave es la última pregunta, la que tiene como respuesta 40.

Si en una pregunta hay un dígito que se repite y en la clave ese dígito aparece una sola vez o al revés, muerto tiene prioridad sobre herido. Un ejemplo de estas situaciones se da en las partidas anteriores en la preguntas nº 6.

Antes de continuar , sino conoces el juego, conviene familiarizarse con él. He escrito un pequeño script en Python en el que está implementada una versión sencilla del mismo.

Un poco de historia

El juego tiene probablemente más de 100 años. En español también se conoce como Picas y Fijas o Punto y Fama, mientras que en inglés su nombre más popular es Bulls and Cows, literalmente Toros y Vacas. Hay una adaptación con el nombre Mastermind que usa unas piezas de diversos colores para representar la clave y otras piezas negras y blancas para representar los muertos y heridos. Esta versión inventada por Mordecai Meirowitz en 1970 y comercializada inicialmente en el Reino Unido por Invicta ha sido desde entonces un gran éxito de ventas en todo el mundo. En la actualidad es fácil todavía encontrarlo en las tiendas de juguetes.

Estrategias de resolución

¿Qué estrategias se pueden emplear para resolverlo? Para contestar esta pregunta hay que diferenciar entre humanos y ordenadores ya que las estrategias que pueden utilizar estos últimos no suelen ser fáciles de emplear por los humanos.

Dos estrategias para humanos

Estrategia 1

Es muy fácil de usar pero poco eficiente. Primero se determinan los dígitos presentes en la clave y a continuación el lugar que ocupa cada uno.
Para determinar que dígitos hay, se hacen preguntas con los 4 dígitos iguales: 9999, 8888, 7777, y así sucesivamente hasta determinar los 4 o llegar a 1111. En este último caso los que faltan son ceros.
Una vez conocidos los dígitos que forman la clave se determina su posición empezando por los que no se repiten. Se hacen preguntas en las que aparece el dígito del que se quiere conocer su posición y otros 3 dígitos de los que se sabe que no están en la clave. Si no hay ninguno repetido y en el caso más desfavorable se necesitarán 3 preguntas para conocer la posición del primero, 2 para conocer la posición del segundo y una para conocer la posición del tercero.
En total y en el caso más desfavorable necesitaremos 16 preguntas para determinar la clave. En las Fig. 3. y 4. se ven dos casos en los que se aplica esta estrategia. El primero representa la situación más desfavorable.

Estrategia 2

No es tan fácil de aplicar como la anterior pero es mucho más eficiente. En esta estrategia también se deducen primero los dígitos que hay en la clave y luego se determina el orden en que se encuentran.
Se empieza con una pregunta con cuatro dígitos diferentes que luego se verá que es la más eficiente. A partir de aquí, en general, para obtener una nueva pregunta, se substituye un dígito de la pregunta anterior, en este caso abcd, por uno de los que todavía no han intervenido. La siguiente pregunta sería entonces, abce. La idea que está detrás de este procedimiento es poder hacer deducciones fácilmente con cada respuesta.
Las deducciones se realizan de acuerdo con las reglas siguientes:
Si para la pregunta abcd la respuesta es m1h1 y para la pregunta siguiente abce la respuesta es m2h2, la relación entre m1 + h1 y m2 + h2 es necesariamente una de las siguientes:

m1 + h1 > m2 + h2
m1 + h1 < m2 + h2
m1 + h1 = m2 + h2

En el primer caso d está en la clave y e no. En el segundo caso sucede lo contrario d no está y e si. En el tercer caso se siguen haciendo preguntas del tipo abcf, abcg, … hasta que en la enésima pregunta abck suceda que:

m1 + h1 ≠ mn + hn

Si agotamos los dígitos antes de que se cumpla la condición anterior, repetimos uno de los dígitos que había en la pregunta anterior. Cuando al final se cumpla la condición, hay dos posibilidades:

m1 + h1 > mn + hn
m1 + h1 < mn + hn

En el primer caso k no está en la clave pero todos los dígitos anteriores, d, e, f, … , si lo están. En el segundo caso, k está en la clave pero todos los dígitos anteriores, d, e, f, … no.
Hay ocasiones en que antes de que se cumpla la condición mencionada, m1 + h1 ≠ mn + hn, ya se pueden extraer conclusiones. Al llegar a la pregunta número 6 – (m + h), se puede concluir que no están todos los números que hemos ido cambiando incluido el primero. En la figura adjunta se muestra un ejemplo de esta situación.

En el ejemplo mostrado, al llegar a la pregunta 5 (6 – (1+0)) se puede deducir que no están en la clave los dígitos 4, 5, 6, 7 y 8.
Por cierto, en la pregunta 11 ya se puede deducir la clave. ¿cuál es?. La solución al final de la entrada.

Para poder obtener información también sobre la colocación de los dígitos, en cada nueva pregunta se pueden ir cambiando las posiciones de los dígitos. Una forma sencilla seria, por ejemplo mover cada dígito una posición a su derecha pasando el último a la primera posición.

Después de llegar a alguna conclusión sobre dígitos que están o no están en la clave se hace una pregunta en la que se incluyen todos los dígitos que se sabe que están y se eliminan todos aquellos que se sabe que no están. Para organizar la información es conveniente hacer unas listas en las que se anota lo que se sabe sobre los dígitos. Por ejemplo:

Dígitos que están en la clave
Dígitos que no están en la clave
Dígitos de los que todavía no tenemos información. (No se han incluido en ninguna pregunta)

Una vez deducidos los 4 dígitos presentes es fácil que con las preguntas ya realizadas o como mucho con 1 o 2 más se pueda deducir el orden.
En las figuras 6 y 7 se muestran ejemplos de aplicación de esta estrategia,

Al lado de alguna pregunta está la información que en ese momento se puede obtener de las respuestas.
Hay una serie de deducciones que a veces acortan el número de preguntas. Por ejemplo, llamando a los muertos, m, y a los heridos, h:

Si m + h = 0 → los 4 dígitos no están en la clave.
Si m + h = n → si n dígitos de la pregunta están en la clave el resto no lo está.
Si m + h = n → si 4 − n dígitos de la pregunta no están en la clave el resto si lo está.

20 Problemas de Muertos y Heridos

Una buena forma de mejorar en el juego es resolviendo problemas. En el PDF adjunto hay 20 problemas en los que hay que deducir la clave a partir de las preguntas y respuestas dadas. Están generados poniendo a jugar un programa como el que aparece más arriba, que hace de cifrador, con otro que implementa una estrategia de descifrador. Se escogen solo aquellas partidas después de las preguntas y respuestas dadas solo queda una clave posible.

20 problemas de Muertos y Heridos . [Ver Soluciones]

En la entrada siguiente se continúa con el análisis de estrategias para ordenadores.

Solución al problema propuesto más arriba

Única clave posible: 1111

Más información

Sobre la versión de Invicta: Mastermind

Ault, Leslie .H. 1976. The official Master Mind Handbook. (London:New English Library)