Se sabe desde los años 1850 (o incluso mucho antes) que se pueden colocar 5 reinas en un 8*8 de manera que todas las casillas del tablero se encuentran en la misma fila, columna o diagonal que al menos una de las reinas. También se "sabía" que esto no se podía hacer con 4 reinas. Pero no he podido obtener o rastrear alguna prueba matemática rigurosa de esto que pudiera ser (o pudiera haber sido) llevada a cabo en un tiempo razonable por un ser humano con lápiz y papel. Hay en total 635376 formas de colocar 4 reinas en un tablero de ajedrez de 8*8. ¿Alguien conoce un algoritmo combinatorio que aproveche las simetrías del del tablero de ajedrez, que reduzca el número de casos a considerar a cientos (o, como mucho, a miles). miles). Se trata, por supuesto, de un problema trivial para los ordenadores modernos, que muchas veces han verificado que se necesitan 5 reinas.
Respuestas
¿Demasiados anuncios?
El problema de encontrar el número mínimo de reinas necesario para cubrir un tablero de n por n es el problema de dominación de reinas. Según http://ajc.maths.uq.edu.au/pdf/15/ocr-ajc-v15-p145.pdf Aunque en la actualidad no hay actualmente ninguna prueba matemática de que estos valores [los números mínimos conocidos de reinas] son correctos, han sido verificados por ordenador".
Según http://www.combinatorics.org/Volume_8/PDF/v8i1r29.pdf , "...el conocimiento actual de que [entre otras cosas, el número de dominación de las reinas para un tablero de 8 por 8 es mayor que 4], proviene de una búsqueda exhaustiva".
El número de arreglos fundamentales que hay que comprobar para demostrar que no hay solución con 4 reinas es de aproximadamente $\frac{1}{8}{64 \choose 4}\sim 10^5$ como señaló Mark Meckes en su comentario.
Este número puede reducirse en gran medida si optamos por inspeccionar el espacio de soluciones con $5$ reinas. Claramente, cada hipotética $4$ La solución de las reinas genera una familia de $5$ soluciones de las reinas (sólo hay que colocar el $5$ a la reina en cualquiera de los $60$ plazas libres restantes).
Ahora, sólo hay $638$ acuerdos fundamentales con $5$ reinas. Todo $4860$ Se pueden obtener soluciones a partir de las disposiciones fundamentales mediante rotación y reflexión. Al parecer, A.M. Yaglom e I.M. Yaglom lo calcularon por primera vez "a mano" (véase "A través del tablero: Las matemáticas de los problemas del tablero de ajedrez" por John J. Watkins). Parece una tarea bastante factible comprobar que no se puede eliminar una reina en ninguno de esos arreglos y seguir obteniendo un arreglo dominante.
También me pregunto si la formación se produjo antes o después de 1990, porque es cuando Spencer llegó a la cota inferior de n=11. Sé de primera mano que se pueden buscar formaciones a mano para, digamos, hasta n=20 con resultados razonables (nótese que es muy diferente a la prueba real de que la formación es mínima, ya que si encontramos la formación sólo hemos encontrado un límite superior). Así que es muy posible que alguien haya encontrado la formación primero, y entonces Spencer podría haber sido el primero en observarla. Por supuesto, también es posible que el límite de Spencer fuera el primero.
El comentario del Dr. Chatham me ha parecido lo suficientemente interesante como para votarlo, aunque viendo que me he quedado en una reputación, no puedo.
