Problema del caballo de ajedrez
Estimado:
Tengo el siguiente problema que he tratado de resolver y no he podido. Cualquier ayuda será muy bien recibida. Gracias
Federico y Jenaro participan en el siguiente juego en un tablero de mxn , donde m y n debe ser mayor o igual a 2. Federico comienza por la elección de una casilla y pone un caballo en la casilla elegida, a continuación Jenaro y Federico alternativamente mueven el caballo, comenzando por Jenaro, con la restricción de que el caballo no puede caer sobre las casillas que ya han sido visitadas. Pierde cuando no se puede mover el caballo. Determinar, en función de m y n, cual jugador tiene estrategia para ganar el juego, sin importar los movimientos del otro jugador y muestre como el debe jugar para ganar.
NOTA: cada movimiento de un caballo es ir a dos casillas de forma vertical u horizontal y luego a una casilla en la dirección perpendicular.
Tengo el siguiente problema que he tratado de resolver y no he podido. Cualquier ayuda será muy bien recibida. Gracias
Federico y Jenaro participan en el siguiente juego en un tablero de mxn , donde m y n debe ser mayor o igual a 2. Federico comienza por la elección de una casilla y pone un caballo en la casilla elegida, a continuación Jenaro y Federico alternativamente mueven el caballo, comenzando por Jenaro, con la restricción de que el caballo no puede caer sobre las casillas que ya han sido visitadas. Pierde cuando no se puede mover el caballo. Determinar, en función de m y n, cual jugador tiene estrategia para ganar el juego, sin importar los movimientos del otro jugador y muestre como el debe jugar para ganar.
NOTA: cada movimiento de un caballo es ir a dos casillas de forma vertical u horizontal y luego a una casilla en la dirección perpendicular.
1 Respuesta
Respuesta de Valero Angel Serrano Mercadal
El problema que describes es bastante complicado. Para empezar no das unas dimensiones concretas del tablero, quizá deberías conformarte en principio con unas dimensiones fijas, como las del tablero 8x8 del ajedrez u otra cifra fija.
Luego piensa que en el primer movimiento se puede mover hasta a 8 sitios, en el segundo hasta 7 y en los sucesivos hasta siete también. A pocos movimientos que efectúes te vas a dar cuenta que es imposible llevar en la cabeza todas las combinaciones que puede haber, ya que el contrario dispone de varias jugadas. Veo factible que mediante un programa de ordenador iterativo o recursivo (tanto monta monta tanto) se pudiera averiguar qué jugada es la buena para no perder. Tampoco sé cuanto tiempo de cálculo sería necesario, no sea que nos fuéramos a un tiempo prácticamente infinito. Si el programa se ejecutara sobre todas las casillas podría tal vez calcularse cuáles son las casillas buenas y malas. Y la estrategia sería la de los cálculos efectuados por la máquina, no veo factible que una persona pueda albergar todas las combinaciones que puedan darse.
Sobre la complejidad del programa informático no puedo decirte ahora. En tiempos hice algún programa de ese tipo, pero ahora ya perdí la práctica. Y sencillo, lo que se dice sencillo, no lo es, a menos que seas un experto en ese tipo de programación. Aparte está el handicap de que los cálculos se hiciesen infinitos.
Y por deducción matemática no lo veo posible, la complejidad del movimiento del caballo hace que la disposición de casillas libres no sea sencilla de prever.
Y eso es todo lo que se me ocurre en un primer momento.
Luego piensa que en el primer movimiento se puede mover hasta a 8 sitios, en el segundo hasta 7 y en los sucesivos hasta siete también. A pocos movimientos que efectúes te vas a dar cuenta que es imposible llevar en la cabeza todas las combinaciones que puede haber, ya que el contrario dispone de varias jugadas. Veo factible que mediante un programa de ordenador iterativo o recursivo (tanto monta monta tanto) se pudiera averiguar qué jugada es la buena para no perder. Tampoco sé cuanto tiempo de cálculo sería necesario, no sea que nos fuéramos a un tiempo prácticamente infinito. Si el programa se ejecutara sobre todas las casillas podría tal vez calcularse cuáles son las casillas buenas y malas. Y la estrategia sería la de los cálculos efectuados por la máquina, no veo factible que una persona pueda albergar todas las combinaciones que puedan darse.
Sobre la complejidad del programa informático no puedo decirte ahora. En tiempos hice algún programa de ese tipo, pero ahora ya perdí la práctica. Y sencillo, lo que se dice sencillo, no lo es, a menos que seas un experto en ese tipo de programación. Aparte está el handicap de que los cálculos se hiciesen infinitos.
Y por deducción matemática no lo veo posible, la complejidad del movimiento del caballo hace que la disposición de casillas libres no sea sencilla de prever.
Y eso es todo lo que se me ocurre en un primer momento.
