Fuerza bruta en .net para resolver las cifras del concurso cifras y letras

Hacía tiempo que no me ponía a mi mismo un reto de programación y el otro día viendo en la tele el programa cifras y letras me animé a hacer una aplicación que resolviese la sección de cifras. Primero me leí las normas y luego empecé a pensar cómo resolver este tipo de problema. Buscando por Internet encontré estos artículos: (uno, dos y tres) donde de 30.965.760 combinaciones posibles entre los 6 números y sus cuatro operaciones se reduce a 488.642 combinaciones. Además me encontré con dos páginas que resuelven el problema on-line: esta y esta (ambas usando la técnica de backtracking).

Como mi objetivo era hacerlo mediante fuerza bruta, la técnica de backtracking me pareció lo mejor para abordar el problema. Se crea un árbol donde cada nodo contendrá los números con los que se operan, la operación que ha generado ese nodo y el resultado de la misma (excepto el primer nodo que sólo contiene el conjunto de números original).

Vamos combinando uno por uno todos los números con todas las operaciones para encontrar el resultado que buscamos. El orden de las operaciones es suma, resta, multiplicación y división. Como esto puede generar una ingente cantidad de cálculos, podemos podar (acotar) el árbol para reducir estos y el tiempo empleado. Esto se consigue eliminando aquellos casos que no deben darse: En la resta que el resultado sea 0, en la división que el divisor sea 1 o que el resto sea distinto de 0 y que en la multiplicación uno de los factores sea 1. Para evitar números negativos en la resta o que el divsor sea mayor que el dividendo ponemos primero el mayor y después el menor en la operación.

A medida que vamos avanzando en la profundidad del árbol, el conjunto de números con los que operar se irá reduciendo ya que cada pareja de números se convertirá en uno por la operación matemática que se les aplique, siendo esto así recursivamente hasta que sólo haya un número, momento en el cual si el resultado no coincide con el esperado, se retrocede un nodo y se continúa con las siguientes combinaciones.

Para entenderlo mejor un gráfico donde dado un conjunto de tres números (1, 2 y 3) debemos operar con ellos hasta que obtengamos 7 como resultado:


En el ejemplo después de buscar varias combinaciones entre sumas y restas (puntos suspensivos en el gráfico) hemos llegado a las combinaciones de multiplicaciones. Existen tres combinaciones de multiplicaciones: Op: 1 * 2 (que no he puesto en el gráfico por simplificarlo), Op: 1 * 3 y Op: 2 * 3.

  • En el nodo de la multiplicación de 1 * 3 el resultado (Res:) es 3 y no 7 como andamos buscando por lo que hay que seguir calculando. El conjunto de números de este nodo se ha reducido de Nu: 1, 2, 3 a Nu: 2, 3.
    • A continuación hay que crear otro nodo con la suma de los únicos números que quedan: 2 + 3, pero el resultado es 5 con lo que volvemos al nodo anterior.
    • Vamos a hacer la resta: 3-2, pero sigue sin servirnos el resultado, por tanto volvemos al nodo anterior.
    • Hacemos la multiplicación: 2 * 3, pero seguimos igual, por lo que nos vamos al nodo anterior.
    • La división se descarta porque 3 / 2 no dá como resto 0, con lo que no se crea ese nodo y se vuelve al anterior (que en este ejemplo es el principal).
  • Continuamos con la creación del nodo de la multiplicación de 2 * 3 donde el resultado (Res:) es 6 y no 7 como andamos buscando por lo que hay que seguir calculando. El conjunto de números de este nodo se ha reducido de Nu: 1, 2, 3 a Nu: 1, 6.
    • Hay que crear otro nodo con la suma de los únicos números que quedan: 1 + 6, y como el resultado es 7, que es el que buscábamos, ya no hacemos ninguna operación más y vamos retrocediendo por todo el árbol (que os recuerdo que se ha construido mediante una función recursiva) hasta salir de la función que lo ha generado.

El nivel de profundidad de los árboles depende de la cantidad de números inicial. Si son un conjunto de 3 números la profundidad será de 3 niveles, si es de 6 pues … ya sabeis la respuesta 🙂

Como se trata de una estructura de árbol, cada nodo debe tener un puntero al siguiente nodo para trazar un camino desde el nodo inicial hasta el nodo que contiene el resultado que buscamos (en el cual el puntero estará vacío).  Dado que hemos aplicado la técnica de backtracking los nodos que previamente hayamos calculado y no pertenezcan a ese camino desaparecerán porque no nos sirven. Finalmente mediante un bucle recorreremos todos los nodos del camino mostrando por pantalla la operación que lo ha creado hasta el nodo final. Así en el ejemplo quedaría:

Sin embargo en el juego de cifras y letras si no se encuentra el número exacto se puntúa el número que más se acerque a este. La problemática aquí es que con el bactracking, si no se encuentra el número exacto, el camino que se habrá generado cuando retorne la función es el de la última operación, que con toda probabilidad no será el camino hacia el número que más se aproxime al original.

En este caso tenemos dos posibles formas de solucionarlo:

  • A medida que vamos generando los nodos debemos comparar el resultado con el número que buscamos, si se acerca más que el anterior valor que hayamos comparado guardamos este resultado como el número que más se aproxima al buscado. Después cuando haya salido de la función y no se haya encontrado el exacto, se vuelve a llamar a esta misma pero buscando en esta ocasión el resultado aproximado (ya que tenemos la certeza de que se puede calcular) obteniendo así el camino hasta llegar al que más se acerca.
  • El problema de la solución anterior es que tenemos que llamar dos veces a la función que genera el árbol: una para buscar el exacto y otra para buscar el aproximado. Lo ideal es ir guardando un camino alternativo hacia el número aproximado, para que, en caso de no hallar el exacto, recorrer el camino alternativo mediante un bucle para mostrar las operaciones que obtengan el número aproximado. Todo desde la misma llamada a la función. Esto provoca que también se necesite un puntero al nodo anterior.

Aquí dejo el código fuente en C# que pone en práctica todo lo comentado. Se trata de una aplicación de consola donde como parámetros se le pasa todo el conjunto de números separados por espacio y como último número el resultado que se desea averiguar.

Program.cs:

Nodo.cs:

También podéis descargaros el ejecutable del programa para poder hacer las pruebas.

Así por ejemplo este reto:

Se resuelve como:

4 comentarios en “Fuerza bruta en .net para resolver las cifras del concurso cifras y letras

  1. Caramon

    Es una buena primera aproximación, pero en realidad te dejas a un lado otro set de operadores. Por ejemplo:

    Sumo 3 + 7 por un lado

    Sumo 4 + 2 por otro

    Multiplico los resultantes (10 * 6)

    ¿Se podría llegar a 60 utilizando cada uno de los 4 números por su cuenta y con las operaciones previstas?… Problema para el programa 😉

    En realidad, deberíamos considerar cualquier par de números producto cartesiano con las operaciones como otros posibles operadores, e incluso cada trio o n-tupla.

    Así te dará mejores soluciones (o más cercana), pero necesita de mucha más fuerza.

    Responder
    1. admin Autor

      En principio eso es lo que hace, he probado lo que me dices y esto es lo que sale:

      C:\temporal>Cifras.exe 3 7 4 2 60
      Set de números: 3 7 4 2
      Número buscado: 60

      Se encontró el exacto.

      Número de nodos calculados: 39
      Tiempo en calcularlo: 11,0011 ms.

      Operaciones:
      3+7=10
      4+2=6
      10*6=60

      Desde luego no siempre la solución es la que un humano pensaría hacer intentando sacar el menor número de operaciones, ya que computacionalmente es más rápido buscar la primera solución que la más optima.

      Responder
  2. Caramon

    Ah, cojonudo entonces, no me había dado la impresión por el post de que también fuera capaz de agrupar, y por tiempo no pude leerme el código a fondo 🙁

    Pues nada, ahora a ir al programa y a hacerse ricos! 😉

    Responder

Responder a admin Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *