Cómo funciona 8 reinas

Dependiendo de los círculos en los que te encuentres, por ejemplo, tu mejor amigo es un programador de computadoras y tu hermana es un prodigio del ajedrez, es posible que ya estés familiarizado con el rompecabezas de las 8 reinas. Para el resto de nosotros, el rompecabezas de las 8 reinas (o problema o simplemente "8 reinas") probablemente no sea algo en lo que dediquemos mucho tiempo a pensar.

El rompecabezas es bastante simple. ¿Cómo puedes colocar 8 reinas en un tablero de ajedrez para que no se ataquen dos? Alternativamente, la pregunta a veces se formula como "¿Cuál es la cantidad máxima de reinas que se pueden colocar en un tablero de ajedrez, de modo que dos no puedan atacarse entre sí?", pero este acertijo se vuelve mucho menos difícil cuando lo buscas en Google , y el término Aparece "el rompecabezas de las 8 reinas".

Es posible que se pregunte por qué diablos a alguien le importa dónde guarda sus ocho reinas. Y sí, superficialmente, es solo un rompecabezas estratégico. Pero (y aquí es donde es útil tener un mejor amigo que codifica computadoras) el rompecabezas de las 8 reinas es una excelente manera de probar la inteligencia y la alfabetización de un programador.

Ahora, no tengas miedo. No se verá obligado a comprender las complejidades de la programación informática para poder seguir leyendo. Pero debe saber que se puede resolver el rompecabezas usando un código de programación, y algunos son más elegantes que otros. Por ejemplo, definitivamente puede encontrar la solución utilizando un programa de "fuerza bruta" que podría simplemente pasar por todas las ubicaciones posibles, descartando una a la vez. Pero un codificador sofisticado podrá construir un programa que tenga atajos usando un algoritmo más refinado para encontrarle una solución más rápido. Ser capaz de idear formas inusuales u originales de codificar una solución a un problema tan amplio como 8 Queens puede ser una gran prueba para el conocimiento de un escritor de código.

Entonces, aunque no te estaremos encadenando 1 y 0 para explicarte cómo funciona 8 Queens, te daremos algunas soluciones al rompecabezas.

Ahora que tenemos la premisa básica del rompecabezas, debemos establecer por qué el problema es tan único. Para hacer eso, repasemos nuestros conceptos básicos de ajedrez. En un juego de ajedrez, la reina es una fuerza a tener en cuenta. Puede moverse en línea recta vertical, horizontal o diagonalmente, tantos espacios como quiera. El único inconveniente es que no puede saltar piezas, por lo que si un peón se interpone en su camino, debe capturarlo y detenerse.

Esto es lo que hace que el rompecabezas de las 8 reinas sea interesante. Si las reinas pueden moverse hacia arriba, hacia abajo, hacia la izquierda, hacia la derecha y en diagonal, ¿cuántos miembros de la realeza en guerra pueden ocupar el tablero sin compartir la misma fila, columna o línea diagonal? Ahora, podría pensar que sería una excelente idea simplemente colocar una reina en el tablero, probando diferentes combinaciones antes de acertar con todas. Y claro, eso es posible. Pero hay 4.426.165.368 soluciones potenciales, por lo que podría considerar encontrar un atajo.

Antes de colocar nuestras reinas en 4 mil millones de cuadrados diferentes, primero reconozcamos que alguien se sentó un día y decidió que esta sería una buena forma de desperdiciar una o dos tardes. Como era de esperar, no era alguien que tenía reposiciones de "My Big Fat Gypsy Wedding" para ponerse al día: era un maestro de ajedrez y compositor alemán del siglo XIX llamado Max Bezzel. (Un compositor de ajedrez es alguien que crea problemas de ajedrez, también conocidos como acertijos, para resolverlos). Apareció por primera vez en la revista alemana de ajedrez DieSchachzeitung en 1848.

Bezzel no estaba tan interesado en resolver el rompecabezas; estaba satisfecho con simplemente plantear la pregunta. Sin embargo, en 1850, el matemático Franz Nauck escribió otro artículo que discutía el problema. (Las primeras soluciones al rompecabezas finalmente fueron resueltas por Nauck). Eso llamó la atención de Karl Gauss, un matemático del siglo XIX conocido por descubrir la teoría fundamental del álgebra. Cuando Gauss se interesó en encontrar la solución, otros lo siguieron y comenzaron a surgir diferentes enfoques para resolver el rompecabezas.

No es una gran sorpresa que "ocho" sea la respuesta a nuestra pregunta específica de cuántas reinas se pueden colocar en un tablero sin atacarse entre sí. Pero exploremos de cuántas maneras se pueden colocar ocho reinas y cómo se establece.

Hablamos sobre cómo los programas de computadora de fuerza bruta son una forma de resolver el rompecabezas, y probar 4,426,165,368 posibilidades manualmente ciertamente calificaría como fuerza bruta, pero hay formas más fáciles de reducir las soluciones. Se proporcionó un método simplificado cuando JWL Glaisher, otro matemático, publicó un artículo en 1874 que describía su uso de determinantes para encontrar una solución. "Determinantes" suena un poco difícil, pero todo lo que realmente necesita saber es que Glaisher básicamente construyó una matriz y, usando un sistema que derivó de esa matriz, pudo reducir las posibles soluciones a 92.

Y quedan 92 soluciones. Pero no se deje engañar; no podrá alinear 92 tableros de ajedrez, cada uno con un conjunto único de 8 reinas resueltas pacíficamente, porque en realidad solo hay 12 soluciones únicas.

¿Confundido? La diferencia entre 12 soluciones únicas y 92 soluciones fundamentales se basa, literalmente, en cómo lo mires. Si bien puede configurar 12 tableros diferentes de manera distintiva con sus ocho reinas, todo lo que necesita es que simplemente gire el tablero, o incluso lo refleje en un espejo, para que los tableros se vean técnicamente diferentes y, por lo tanto, tengan un "diferente". solución. (Esto se llama operaciones de simetría rotacional y reflexiva.) Así que tomas tus 12 tableros únicos, los giras 90, 180 y 270 grados y luego los reflejas en cada rotación. Pero una cosa más: una placa única es simétrica, por lo que se ve igual desde dos ángulos. Mientras que todos los demás tableros tienen ocho variantes, el tablero simétrico solo tiene cuatro. Entonces, en lugar de 12 tableros por 8 variaciones (96), en realidad estamos restando los cuatro que no existen con el tablero simétrico. ¿Qué obtenemos? 92 soluciones fundamentales.

Ahora, no dejes que las matemáticas te engañen. Siempre puede encontrar un tablero de ajedrez e intentar descubrir algunas ubicaciones por sí mismo. (Encontrar una respuesta, por supuesto, es mucho más fácil que encontrar las 12). E incluso hay programas en la Web que le permiten descubrir algunas soluciones diferentes. (Advertencia: pueden hacerte sentir estúpido).

Antes de barajar las reinas, consulte la siguiente página para obtener más información.

Siendo una persona menos interesada en un algoritmo que en un alfabeto, no tenía muchas esperanzas de entender el rompecabezas de las 8 reinas. Aunque estaba seguro de que tenía algún tipo de aplicación práctica, no pude verlo. Irónicamente, fue cuando entendí la inmensidad del problema que comencé a ver por qué podría ser útil. Encontrar un conjunto de soluciones a partir de una gran cantidad de posibilidades es una de las razones por las que existe el código. El problema de las 8 reinas desafía a programadores y matemáticos por igual a descubrir técnicas novedosas para simplificar la búsqueda.

enlaces relacionados

Fuentes