Buscando "El símbolo perdido" con LINQ (II)

“Now I know you’re all king horse
Between tenderness and brute force…”
(“King Horse”, Elvis Costello, 2007)

Continuando con el problema propuesto en el post anterior (basado en “El símbolo perdido“, la última obra de Dan Brown), aquí presento el código final utilizado para resolver el problema, así como un análisis somero de los resultados obtenidos.

La adición de las condiciones que faltan al programa del post anterior (que la suma de los cuatro “cuadrantes”, más la del cuadrado central, coincida con la de las filas, columnas y diagonales) nos permite reducir el número de “variables libres” sobre las que el programa debe iterar a 7, con lo que la cantidad de combinaciones a probar es del orden de MAX^7, donde MAX es el valor máximo que queremos poder almacenar en cualquier casilla.Inicialmente establecí MAX a 100, con lo que el número de combinaciones a intentar era realmente enorme. Pero el problema resultó más “flojo” de lo que pensaba: en unos dos días de cálculo ininterrumpido, Rainmaker ya había encontrado unas 500.000 soluciones, y el valor de la primera variable (a11) aún seguía siendo 1. Así que decidí no torturar más al pobre amigo y detuve la ejecución. A continuación, el primero de los cuadrados obtenidos:

1 4 11 29
26 14 3 2
12 7 21 5
6 20 10 9

Entonces decidí restringir la búsqueda a los cuadrados en los que el número máximo utilizado fuera el 20, lo que redujo considerablemente la cantidad de combinaciones a probar. En algo menos de un minuto, ya tenía a mi disposición los 320 cuadrados válidos existentes. De nuevo, aquí solo muestro el primero de ellos; el lector interesado en buscar uno más “bonito” puede ejecutar el programa y estudiar sus resultados.

11 1 13 19
18 14 4 8
3 9 17 15
12 20 10 2

Así que aquí está mi modesto homenaje a Visual Studio 2010 – un programa que utiliza LINQ y que se me antoja combina, usando las palabras de Elvis Costello, “ternura y fuerza bruta” (pero, ¿en qué medida cada una de ellas, amigo lector? 🙂 .

Código utilizado:

using System;
using System.IO;
using System.Linq;

namespace LostSymbol
{
    class Program
    {
        private const int MAX = 20;

        static void Main(string[] args)
        {
            const int firstSeed = 20;
            const int secondSeed = 10;

            var res =
                /* first row */
                from a11 in Enumerable.Range(1, MAX)
                where a11 != firstSeed && a11 != secondSeed
                from a12 in Enumerable.Range(1, MAX)
                where a12 != firstSeed && a12 != secondSeed &&
                      a12 != a11
                from a13 in Enumerable.Range(1, MAX)
                where a13 != firstSeed && a13 != secondSeed &&
                      a13 != a11 && a13 != a12
                from a14 in Enumerable.Range(1, MAX)
                where a14 != firstSeed && a14 != secondSeed &&
                      a14 != a11 && a14 != a12 && a14 != a13
                let sum = a11 + a12 + a13 + a14
                /* second row */
                from a21 in Enumerable.Range(1, MAX)
                where a21 != firstSeed && a21 != secondSeed &&
                      a21 != a11 && a21 != a12 && a21 != a13 && a21 != a14
                let a22 = sum – (a11 + a12 + a21)
                where a22 > 0 && a22 <= MAX &&
                      a22 != firstSeed && a22 != secondSeed &&
                      a22 != a21 &&
                      a22 != a11 && a22 != a12 && a22 != a13 && a22 != a14
                from a23 in Enumerable.Range(1, MAX)
                where a23 != firstSeed && a23 != secondSeed &&
                      a23 != a21 && a23 != a22 &&
                      a23 != a11 && a23 != a12 && a23 != a13 && a23 != a14
                let a24 = sum – (a21 + a22 + a23)
                where a24 > 0 && a24 <= MAX &&
                      a24 != firstSeed && a24 != secondSeed &&
                      a24 != a21 && a24 != a22 && a24 != a23 &&
                      a24 != a11 && a24 != a12 && a24 != a13 && a24 != a14 &&
                      a13 + a14 + a23 + a24 == sum     /* second quadrant */ 
                /* third row */
                from a31 in Enumerable.Range(1, MAX)
                where a31 != firstSeed && a31 != secondSeed &&
                      a31 != a11 && a31 != a12 && a31 != a13 && a31 != a14 &&
                      a31 != a21 && a31 != a22 && a31 != a23 && a31 != a24
                let a32 = sum – (a12 + a22 + firstSeed)
                where a32 > 0 && a32 <= MAX &&
                      a32 != firstSeed && a32 != secondSeed &&
                      a32 != a31 &&
                      a32 != a11 && a32 != a12 && a32 != a13 && a32 != a14 &&
                      a32 != a21 && a32 != a22 && a32 != a23 && a32 != a24
                let a33 = sum – (a13 + a23 + secondSeed)
                where a33 > 0 && a33 <= MAX &&
                      a33 != firstSeed && a33 != secondSeed &&
                      a33 != a31 && a33 != a32 &&
                      a33 != a11 && a33 != a12 && a33 != a13 && a33 != a14 &&
                      a33 != a21 && a33 != a22 && a33 != a23 && a33 != a24 &&
                      a22 + a23 + a32 + a33 == sum     /* middle quadrant */
                let a34 = sum – (a31 + a32 + a33)
                where a34 > 0 && a34 <= MAX &&
                      a34 != firstSeed && a34 != secondSeed &&
                      a34 != a31 && a34 != a32 && a34 != a33 &&
                      a34 != a11 && a34 != a12 && a34 != a13 && a34 != a14 &&
                      a34 != a21 && a34 != a22 && a34 != a23 && a34 != a24
                /* fourth row */
                let a41 = sum – (a11 + a21 + a31)
                where a41 > 0 && a41 < MAX &&
                      a41 != firstSeed && a41 != secondSeed &&
                      a41 != a11 && a41 != a12 && a41 != a13 && a41 != a14 &&
                      a41 != a21 && a41 != a22 && a41 != a23 && a41 != a24 &&
                      a41 != a31 && a41 != a32 && a41 != a33 && a41 != a34 &&
                      a41 + a32 + a23 + a14 == sum &&    /* right-to-left diagonal */
                      a31 + a32 + a41 + firstSeed == sum     /* fourth quadrant */
                let a42 = firstSeed
                let a43 = secondSeed
                let a44 = sum – (a14 + a24 + a34)
                where a44 > 0 && a44 < MAX &&
                      a44 != firstSeed && a44 != secondSeed &&
                      a44 != a41 &&
                      a44 != a11 && a44 != a12 && a44 != a13 && a44 != a14 &&
                      a44 != a21 && a44 != a22 && a44 != a23 && a44 != a24 &&
                      a44 != a31 && a44 != a32 && a44 != a33 && a44 != a34 &&
                      a41 + firstSeed + secondSeed + a44 == sum &&
                      a11 + a22 + a33 + a44 == sum &&    /* left-to-right diagonal */
                      a33 + a34 + a43 + a44 == sum     /* third quadrant */
                select new
                {
                    a11, a12, a13, a14,
                    a21, a22, a23, a24,
                    a31, a32, a33, a34,
                    a41, a42, a43, a44,
                };

            using (StreamWriter sw = new StreamWriter(“C:\TEMP\Solutions.txt“))
            {
                sw.WriteLine(“Start : ” + DateTime.Now.ToString(“yyyy/MM/dd hh:mm:ss”));
                int n = 0;
                foreach (var r in res)
                {
                    sw.WriteLine(“Solution ” + n);
                    sw.WriteLine(“=============”);
                    sw.WriteLine(“{0} {1} {2} {3}”, r.a11, r.a12, r.a13, r.a14);
                    sw.WriteLine(“{0} {1} {2} {3}”, r.a21, r.a22, r.a23, r.a24);
                    sw.WriteLine(“{0} {1} {2} {3}”, r.a31, r.a32, r.a33, r.a34);
                    sw.WriteLine(“{0} {1} {2} {3}”, r.a41, r.a42, r.a43, r.a44);
                    sw.WriteLine();
                    sw.Flush(); n++;
                }
                sw.WriteLine(“Finish: ” + DateTime.Now.ToString(“yyyy/MM/dd hh:mm:ss”));
            }
            Console.ReadLine();
        }
    }
}


Pop/Rock tip: Elvis Costello, cantante y compositor nacido en Inglaterra, lleva más de treinta años de éxito desde que debutó en 1977 con el excelente album “My Aim is True“. Su eclecticismo musical y letras trabajadas lo han convertido en un referente para varias generaciones de músicos.

Octavio Hernandez

Desarrollador y consultor en tecnologías .NET. Microsoft C# MVP entre 2004 y 2010.

2 comentarios en “Buscando "El símbolo perdido" con LINQ (II)

  1. Octavio, alias Durero II. El resucitador del cuadrado mágico. Pues no hay literatura sobre el mismo. Practicamente todo aficionado/profesional a las matemáticas recreativas les ha echado un tiento.

    Que por cierto fue para lo que yo empecé a estudiar programación: usar un ordenador para hacer matemáticas, cuando ni siquiera sabía que los ordenadores ya se usaban para eso. SI has leído “mi historia de la informática” habrás leído que uno de mis primeros pinitos fue hacer una hoja de cálculo en ensamblador en CP/M (y si no lo dije, lo digo ahora), que por supuesto no terminé porque aparte de que se me rompiera el ordenador no tenía ni conocimientos ni medios.

    Lo que pasa es que en el camino me atrapó el medio y en el medio me quedé, sin llegar al fin. En fin (valga la rebuznancia), así es la vida.

Deja un comentario

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