El caballo de ajedrez salta en L: dos casillas en una dirección y una en perpendicular. El problema que nos ocupa cabe en treinta palabras y arrastra unos mil años de historia documentada: que un caballo visite cada casilla del tablero exactamente una vez. Sin capturas: el rival es el propio tablero, con sus esquinas cerrándose.
Un poema, antes que un teorema
La capa más antigua citable con fuente enlazable es sánscrita. En el Kāvyālaṃkāra —el «adorno de la poesía» del poeta cachemiro Rudrata, del siglo IX— aparece un recorrido de caballo sobre medio tablero, un 4×8, convertido en figura poética: el turagapadabandha, «arreglo en los pasos del caballo». Como el sánscrito se escribe en sílabas, cada sílaba es una casilla: el mismo verso se lee de corrido o siguiendo los saltos («Knight's tour», Wikipedia, versión consultada hoy).
La otra capa antigua no es poema sino tratadística de ajedrez, y viajó por el mundo arabo-musulmán: hacia el 840, el jugador y teórico al-Adlī ar-Rūmī documentaba ya una solución del circuito completo, y un manuscrito copiado en 1141 —que reproduce textos de no más tarde del siglo X— esconde en cuatro poemas de 64 versos otras tantas rutas, asociando cada verso a las coordenadas de una casilla. El problema era popular allí, sin que nadie conociera aún un método general para construirlo («Problème du cavalier», Wikipedia en francés, versión consultada hoy, que resume la investigación del historiador Adhemar Sesiano). Dos capas, dos tradiciones: fundirlas en un único «origen» sería inventarse un país que no existe. Y una nota pendiente: a veces se atribuye un diagrama de recorrido a la prosa árabe «Rūḍat al-ʿāqil»; hoy no hemos podido trazar esa atribución a ninguna fuente enlazable, así que queda, aquí, como [según la tradición] — sin fecha ni sede afirmadas.
1759: el caballo entra en la academia
En Europa el asunto se volvió matemática con Euler. Su memoria «Solution d'une question curieuse qui ne paraît soumise à aucune analyse» lleva fecha de 1759 y se publicó en los Mémoires de la Real Academia de Ciencias y Bellas Letras de Berlín (año 1759, volumen 15, páginas 310-337, impresos en 1766), según cita la misma fuente francesa de arriba; la inglesa data su trabajo en ese mismo 1759. En ella mostró soluciones sistemáticas del recorrido —incluidas simétricas— y extendió el problema a tableros mayores que el de 8×8. El salto dejó de ser un adorno poético: pasó a ser un problema con método.
La regla de 1823, que sigue de moda
El primer procedimiento general para completar un tour lo publicó en 1823 Warnsdorff, en un opúsculo alemán de título impronunciable: «Des Rösselsprungs einfachste und allgemeinste Lösung». La regla vale su peso en tours: salta siempre a la casilla desde la que queden menos salidas libres. Es voraz, se calcula sin papel, y resuelve tableros enteros a la primera casi siempre. (Una cautela de genealogía: las enciclopedias consultadas lo registran «H. C. von Warnsdorff» y otra literatura le da «C. F.»; nadie zanja la disputa con fuente en esta pieza, así que se queda en Warnsdorff, a secas.) En el lenguaje de hoy: lo que busca el caballo es un camino hamiltoniano en el grafo del caballo; el problema general es NP-duro, pero esta versión se resuelve en tiempo lineal (Conrad y otros, 1994, en la misma Wikipedia inglesa). Y para el asombro con cifra exacta: en el 8×8 clásico hay 26.534.728.821.064 recorridos cerrados contando como distintos el inverso, las rotaciones y los reflejos; el recuento lo publicaron Löbbing y Wegener en 1996 y lo corrigió Brendan McKay en 1997.
La regla de 1823 corre hoy en nuestro taller
Cuando fotografiamos este juego para sus manuales no fingimos la partida: la jugamos. Nuestro rig de capturas aplica la regla de Warnsdorff en una búsqueda en profundidad — primero prueba el destino con menos salidas libres y da marcha atrás cuando se atasca —, con un tope de dos millones de movimientos explorados que es solo el seguro por si algún día retratáramos otro tamaño; la nota del resolutor presume, con razón, que en 6×6 el tour se cierra casi siempre sin retroceder ni una vez. Y no pinta los números: los juega casilla a casilla por el mismo receptor de toques del tablero que recibe el dedo del jugador. Precisión debida: el juego no resuelve nada — pide el recorrido al jugador y ni siquiera tiene botón de pista; la heurística de 1823 la usa nuestra herramienta de cámara, no la partida—. Las dos fotos de aquí, la mitad con 18 saltos puestos y el 6×6 completo tras el confeti, salieron de ese tour. El caballo que salta en ellas, por cierto, también es casero: dos figuras SVG dibujadas en casa, una por color, viven con el juego.
Y ahora saltas tú
El Salto del caballo del catálogo va del 5×5 del Fácil al 8×8 del Experto, con la regla de 1823 en la cabeza. El concurso sigue siendo el mismo tras un milenio: pisa cada casilla una sola vez. Y si te atascas a media ruta, ya sabes: ve a la casilla con menos salidas.