El Blog de Antonio Villena ESTOS SON MIS PRINCIPIOS, SI NO TE GUSTAN PUEDO CAMBIARLOS

En realidad resolveré sólo las cifras. Se trata del famoso programa de televisión "Cifras y Letras" que emitía la 2 a comienzos de los 90, o de la versión más reciente que emiten actualmente varios canales autonómicos. La idea me ha venido recientemente al leer el siguiente artículo donde el autor explica un método para resolverlo, y diferentes optimizaciones (partiendo de las 30.965.760 fórmulas acaba reduciéndolas a 1.025.472).

---

En mi caso lo resuelvo por backtracking, de una forma muy parecida a Pedro Reina. Si estáis interesados en el código fuente, os recomiendo mejor el suyo, ya que el mío es prácticamente ilegible debido a las optimizaciones javascript que he usado: simulando recursividad con funciones generadas, eliminando arrays, método de inserción ordenada sólo con IFs...

---

La idea es ir reduciendo el array con los 6 números de partida hasta encontrar la solución. En cada paso generamos un array con un elemento menos, y si al final nos queda un único elemento que coincide con la solución, paramos el algoritmo. Veamos un ejemplo:

---

Número a buscar: 806.
Números con los que jugar: 3, 7, 75, 25, 9, 1
Lo primero que hacemos es construir el array, ordenándolos de mayor a menor [75, 25, 9, 7, 3, 1]. Voy a mostrar dos ejemplos: una rama fallo y la rama solución. En realidad el algoritmo va recorriendo el árbol hasta encontrar la rama solución. En caso de no haber solución se recorre todo el árbol entero, que en mi ordenador suele tardar medio segundo (ten en cuenta que recorre millones de nodos).

---

[75, 25, 9, 7, 3, 1] -> Restamos 1º y 4º elemento, 75-7= 68.
68 -> [25, 9, 3, 1] -> Lo insertamos ordenadamente, 1º.
[68, 25, 9, 3, 1] -> Multiplicamos 2º y 3º, 25*9= 225.
225 -> [68, 3, 1] -> Lo insertamos ordenadamente, 1º.
[225, 68, 3, 1] -> Sumamos los dos primeros, 225+68= 293.
293 -> [3, 1] -> Lo insertamos ordenadamente, 1º.
[293, 3, 1] -> Multiplicamos los dos primeros, 293*3= 879.
879 -> [1] -> Lo insertamos ordenadamente, 1º.
[879, 1] -> Restamos los dos elementos que nos quedan.
[878] -> No coincide con 806, por lo que probamos otra rama.

---

[75, 25, 9, 7, 3, 1] -> Sumamos 1º y 2º elemento, 75+25= 100.
100 -> [9, 7, 3, 1] -> Lo insertamos ordenadamente, 1º.
[100, 9, 7, 3, 1] -> Restamos el 4º al 2º, 9-3= 6.
6 -> [100, 7, 1] -> Lo insertamos ordenadamente, 3º.
[100, 7, 6, 1] -> Sumamos 2º y 4º elemento, 7+1= 8.
8 -> [100, 6] -> Lo insertamos ordenadamente, 2º.
[100, 8, 6] -> Multiplicamos los dos primeros elementos, 100*8= 800.
800 -> [6] -> Lo insertamos ordenadamente, 1º.
[800, 6] -> Sumamos los dos elementos que nos quedan.
[806] -> Ya está, hemos llegado a la solución, salimos y mostramos el recorrido (solución) por pantalla.

---

Las optimizaciones que he aplicado son:

• El hecho de mantener ordenado el array evita tener que duplicar operaciones en sumas y productos. En las restas y divisiones descartamos siempre el caso de que el primer operando sea menor que el segundo.
• Antes de reducir (operando con dos números) compruebo si existe solución descartando cualquiera de los elementos.
• En caso de sumar o multiplicar el primero por cualquier otro, me salto el paso de inserción ordenada, ya que siempre se mantendría al principio.
• Si el resultado de la resta es cero, lo descarto (tener un cero en el array no ayuda a encontrar la solución).
• Si el resto de la división es distinto de cero, también descarto. El número a hallar es entero, y si en la solución arrastro decimales y luego me los quito, existe otra rama (redundante) en la que se llegaría sin arrastrar decimales, por lo que mejor esperamos (y mostramos una solución más elegante).
• Si la operación es multiplicación o división y el segundo operando es 1, también la descarto, puesto que ya hemos probado ese caso.
• Si existen números repetidos, evito calcular de nuevo la rama (esto es fácil de detectar porque los números repetidos siempre están juntos).

---

Los métodos usados para generar los números de partida son distintos en ambos programas de TV. En la versión presentada por Elisenda Roca los concursantes elegían de entre los 4 grupos de 6 fichas, conteniendo los 3 primeros dos juegos de números del 1 al 9, y en el cuarto grupo los números 10, 10, 25, 50, 75 y 100.. En la versión de las televisiones autonómicas los generaba un ordenador, probablemente dando el doble de probabilidad a los números del 1 al 9. En este caso pueden salir más de 2 fichas del 1-9 y más de 1 ficha del 10-100, siendo más difícil llegar al exacto que en la otra versión. Si queréis profundizar más recomiendo el artículo de Macluskey antes citado.

---

Aquí tenéis el juego para que paséis el rato, y aquí el código fuente. La versión descargable es más completa (existen 3 algoritmos de generación y se muestra el tiempo empleado), pero más burda a nivel estético.

---

Edito: (09-07-2011) He sacado una nueva versión que encuentra el número más aproximado si el exacto no existe. Como en la mayoría de los casos es posible llegar al exacto, uso dos algoritmos y una heurística para elegir el algoritmo inicial. La heurística es comparar si el cuadrado del sumatorio de las pistas es menor que el doble del número a hallar. Si falla la heurística y no se puede llegar al exacto, el programa puede tardar varios segundos (se requiere recorrer el árbol 3 veces y 2 de ellas de forma completa).

---

Edito: (05-09-2011) Macluskey ha publicado un tercer artículo en El Cedazo donde se llegan a conclusiones muy interesantes, como que el número objetivo más fácil es el 150 y el más difícil el 967.

---

---

Resolver Generar

---