Allá por el siglo XIX el siguiente problema hizo furor: colocar 8 damas en el tablero sin que se amenacen entre sí. Por ejemplo, en la siguiente posición se han colocado 8 damas con la condición del problema.
Hay 92 soluciones distintas sin contar simetrías. Si se está interesado en encontrar una de estas soluciones, es más fácil colocar una dama en a4 o en a5 que en a1 o en a8 (ya que entonces, una de las dos grandes diagonales quedarían prohibidas). Parece ser que el matemático aleman Gauss se ocupó de este problema.
El problema del caballo consiste en encontrar un ciclo usando los movimientos del caballo de forma que el caballo pase por todos los cuadros del tablero exactamente una vez. Es decir, el caballo parte de cualquier casilla y debe regresar a ella después de completar el tour. En Teoría de Grafos esto se llama "Tour Hamiltoniano" en honor al célebre matemático irlandés William Hamilton y el grafo que cumple esta propiedad se llama Hamiltoniano.
Con los "ojos de un caballo" el tablero de ajedrez sería como muestra la figura adjunta.
El problema de encontrar un tour hamiltoniano, en este grafo, está resuelto y hay numerosas páginas web e incluso vídeos en YouTube como en https://www.youtube.com/watch?v=RG8IB2u1ndM que enseñan cómo hacerlo. La solución no es única.
Aunque este problema, en el grafo del caballo, es fácil de resolver no es así el problema más general, de determinar si un grafo cualquiera es Hamiltoniano. Este problema está clasificado por la teoría de la complejidad algorítmica como NP-completo. En términos coloquiales, esto significa que, muy probablemente, nunca se podrá resolver por un algoritmo de ejecución en tiempo polinómico dependiendo del tamaño del grafo.
Vicente Campos
Se trata de un problema compuesto por Karl Faber.
Blancas juegan y NO dan mate
