Ocho reinas, caballo de Euler, tablero mutilado: los grandes rompecabezas matemáticos del tablero

Estos rompecabezas se juegan con las piezas o con la cuadrícula del tablero, pero no tienen nada que ver con una partida: son auténticos problemas matemáticos, accesibles desde secundaria, y algunos han ocupado a grandes nombres de la disciplina. Son ideales para un club de matemáticas, una exposición o un tema para la prueba oral.

Tabla resumen

El problema de las ocho reinas

Problema de las ocho reinas

Colocar ocho reinas en un tablero de 8 × 8 de manera que ninguna pueda capturar a otra: nunca dos reinas en la misma fila, la misma columna o la misma diagonal.

El problema fue publicado en 1848 por Max Bezzel, compositor de problemas de ajedrez. Franz Nauck publicó las primeras soluciones en 1850 y lo generalizó a n reinas en un tablero de n × n casillas. Carl Friedrich Gauss figura entre los matemáticos que se interesaron por él.

Objetivo del problema: encontrar una disposición y, después, todas. Hay 92. Muchas se deducen unas de otras por rotación o simetría del tablero; si se agrupan, quedan 12 soluciones fundamentales. Aquí tienes una, con las reinas en d8, g7, c6, h5, b4, e3, a2 y f1:

Es fácil comprobar que hay una reina por fila y por columna. Para las diagonales, basta con verificar que, para dos reinas cualesquiera, la diferencia de columnas nunca es igual a la diferencia de filas.

¿Cómo resolverlo?

El método clásico es el retroceso (en inglés, backtracking): se coloca una reina en la primera columna, luego otra en la segunda columna en una casilla no atacada, y así sucesivamente; cuando ninguna casilla es posible, se retrocede y se mueve la reina anterior. Es un ejercicio muy apreciado en las clases de informática de bachillerato. La versión con n reinas tiene soluciones para todo n salvo 2 y 3: por ejemplo, 2 soluciones para n = 4, 10 para n = 5, 4 para n = 6 y 40 para n = 7.

El problema del caballo de Euler

Problema del caballo

Hallar una sucesión de movimientos de caballo que pase una sola vez por cada una de las 64 casillas. El recorrido se dice cerrado si la última casilla está a un salto de caballo de la primera, lo que permite repetir el ciclo.

El problema es muy antiguo: un recorrido del caballo sobre medio tablero ya aparece en un tratado de poética sánscrita del siglo IX, el Kavyalankara de Rudrata. Leonhard Euler le dedicó una memoria, «Solución de una cuestión curiosa que no parece sometida a ningún análisis», presentada en 1759 y publicada en 1766 en las memorias de la Academia de Ciencias de Berlín. En 1823, H. C. von Warnsdorff propuso una regla sencilla para encontrar un recorrido: ir siempre hacia la casilla desde la que el caballo tenga el menor número posible de salidas.

Existe un número gigantesco de recorridos cerrados en el tablero ordinario: 26 534 728 821 064 contando el sentido de recorrido, es decir, la mitad, 13 267 364 410 532, si se considera que un recorrido y su inverso son el mismo.

Un recorrido para comprobar en un tablero de 5 × 5

Para practicar, se puede empezar con un tablero más pequeño. Aquí tienes un recorrido abierto que visita las 25 casillas de un tablero de 5 × 5: sigue los números del 1 al 25; cada número está a un salto de caballo del anterior.

Este recorrido se ha obtenido con la regla de Warnsdorff, y cada salto ha sido comprobado. Reto: encontrar otro que empiece en el centro.

El problema del caballo en la prueba oral

El tema se presta bien a la prueba oral de matemáticas o de NSI en el bachillerato: modelización mediante un grafo (las casillas son los vértices, los saltos posibles son las aristas), búsqueda de un camino que pase por todos los vértices, algoritmo de retroceso, regla de Warnsdorff y su eficacia. También se puede explicar por qué no existe ningún recorrido cerrado en un tablero de 5 × 5: el caballo cambia de color en cada salto, por tanto un ciclo tiene necesariamente un número par de casillas, y 25 es impar.

El tablero mutilado

El filósofo Max Black planteó el problema en 1946 en su libro Critical Thinking. Se quitan dos esquinas opuestas de un tablero (por ejemplo a1 y h8). ¿Se pueden cubrir las 62 casillas restantes con 31 fichas de dominó, cubriendo cada ficha dos casillas contiguas?

Respuesta: no. Cada ficha cubre necesariamente una casilla blanca y una negra. 31 fichas cubrirían, por tanto, 31 casillas blancas y 31 negras. Ahora bien, las dos esquinas opuestas son del mismo color: quedan 32 casillas de un color y 30 del otro. El embaldosado es imposible, sin necesidad de probar ninguna disposición. Martin Gardner dio a conocer este problema al gran público en 1957 en su sección de Scientific American.

¿Y si se quitan una casilla blanca y una negra? Ralph Gomory demostró (resultado publicado en 1973) que el embaldosado es entonces siempre posible, sea cual sea el par de casillas retiradas.

Poliominós y pentominós

Un poliominó es una figura formada por cuadrados idénticos unidos por sus lados; el dominó tiene dos, el pentominó cinco. El matemático Solomon Golomb introdujo y estudió estas figuras a partir de 1953. Existen 12 pentominós distintos (considerando que una pieza girada o volteada sigue siendo la misma), que juntos cubren 60 casillas.

Ahora bien, un tablero tiene 64 casillas, es decir, 60 + 4: se puede intentar colocar los 12 pentominós en el tablero dejando libre un cuadrado de 2 × 2 en el centro. En 1958, Dana Scott hizo resolver este problema por un ordenador, uno de los primeros usos del método de retroceso: existen 65 soluciones. Otro reto célebre: el rectángulo de 6 × 10 puede embaldosarse de 2339 maneras distintas con los 12 pentominós.

¿Cuántos cuadrados hay en un tablero?

La respuesta «64» es falsa, o más bien incompleta: solo cuenta los cuadraditos pequeños. Hay que contar también los cuadrados de 2 × 2, de 3 × 3… hasta el gran cuadrado de 8 × 8.

El total es la suma de los cuadrados de los números del 1 al 8: 1 + 4 + 9 + … + 64 = 204. Para ir más allá: un tablero contiene 1296 rectángulos (incluidos los cuadrados), porque un rectángulo queda determinado al elegir 2 líneas entre las 9 de la cuadrícula y 2 columnas entre 9, es decir, 36 × 36.

Para seguir

Estos problemas movilizan nociones precisas: paridad, coloración, combinatoria, grafos. Los detallamos, con ejercicios para primaria y secundaria, en la página las nociones matemáticas del tablero. Para otros números muy grandes, véase el tablero de Sissa. Y para quienes disfrutan con los acertijos, el blog de Le Palais des Échecs propone los retos de lógica de Le Palais des Échecs, renovados periódicamente.