Otras carreras Problema del caballo

[parasito]

Buenos días amigos, hace un tiempo vi un problema que me llamó la atención, por su simplicidad y belleza. Se trataba del conocido "problema del caballo" o en inglés "Knight's tour". Para quien no lo conozca es simplemente encontrar un recorrido en un tablero de ajedrez, moviendote como lo hace un caballo, en el que partiendo de una casilla cualquiera debes pasar por todas las casillas del tablero, tan solo una vez por cada una de ellas, y regresar a la casilla de salida ( existen otras variantes ).
La cuestión es que en algunas fuentes he visto que no se conoce cuantos circuitos existen ni cuales son, aunque sí que se conocen algunos de ellos.
¿Alguno sabe si esto es cierto? ¿Sabeis si existe algún libro/página/proyecto donde se recoja toda la información posible sobre este problema?

Un saludo y pasen una buena tarde!

[Weip]

Re: Problema del caballo

En la wikipedia lo tienes bastante completo. Eso sí, sólo habla de resolverlo con grafos. Otras demostraciones no sé si son posibles, supongo que sí.

[parasito]

Re: Problema del caballo

Yo me refiero si se conocen ( ya sea matematicamente, por grafos, o computacionalmente ) todas las soluciones posibles de este problema. Vi la información de wikipedia, pero no dice el número de soluciones que existe ni cuales son, o al menos no lo encuentro.

También he visto este artículo de hace 5 años que habla sobre este problema:
http://www.abc.es/20100607/ciencia-t...006071718.html

Es antiguo, pero al final entiendo que dice que no se puede o no se ha sacado un algoritmo para resolverlo en un tiempo polinominal (Problema P).

[Weip]

Re: Problema del caballo

Las soluciones posibles son muchas, pero que muchas. Conocer se pueden conocer, pero como seres humanos que somos tenemos mejores cosas que hacer que pasarnos toda una vida mirando los recorridos del caballo delante de un ordenador.

Luego, el problema sí puede resolverse en un tiempo polinómico. Igual otras variantes no, pero el problema del caballo de toda la vida sí se puede. Piensa que el grafo asociado al movimiento del caballo tampoco es tan grande ni complicado. Para otros grafos en general pues la cosa es más peliaguda.

[parasito]

Re: Problema del caballo

Entonces entiendo que se puede conseguir el número total de soluciones a este problema? es que no encuentro el número por ninguna parte.

[Weip]

Re: Problema del caballo

En al wikipedia inglesa te pone que es la mitad de los ciclos que en el grafo dirigido (en un tablero 8x8). Vamos, que hay $1.3 \cdot 10^{13}$ recorridos posibles, aproximadamente (si quieres más decimales pues haces [FONT=sans-serif]26,534,728,821,064 entre 2)[/FONT].

[parasito]

Re: Problema del caballo

Weip entonces entiendo que computacionalmente este problema (8x8) no tiene ninguna complejidad.
Y sabrías decirme si en un tablero de un orden mayor se podrían conseguir también recorridos (por ordenador)? Por ejemplo,en un tablero 100x100.

Entonces lo que dice el artículo:
[FONT=georgia]"Hoy sabemos que el numero de recorridos posible es realmente muy grande. A pesar de haberse utilizado los más grandes ordenadores disponibles para buscar todas las formas en que el caballo puede recorrer el tablero, no estamos seguros de que los valores hallados sean correctos. Hace 15 años, en 1995, Martin Löbbing e Ingo Wegener pusieron a trabajar 20 ordenadores Sun -potentes para la época- durante cuatro meses y publicaron un documento en el que proclamaban que el número de recorridos posibles en un tablero de 8x8 era 33.439.123.484.294.[/FONT]
[FONT=georgia]Dos años más tarde, en 1997, Brendan McKay encaró el problema del caballo dividiendo el tablero en dos mitades y llego a un resultado algo menor: “sólo” existirían 13.267.364.410.532 recorridos posibles."

dice que no están seguros de que los valores hallados sean correctos. Supongo que esto se ha hecho con ordenadores, como no pueden estar seguros?[/FONT]

[Weip]

Re: Problema del caballo

Weip entonces entiendo que computacionalmente este problema (8x8) no tiene ninguna complejidad.

Pues no mucha. Yo mismo hice en clase un programa en C++ que entre otras cosas te encuentra recorridos para este problema (aunque creo que solo los más cortos... no lo recuerdo muy bien). Y tarda poco (algunos minutos solo).

Y sabrías decirme si en un tablero de un orden mayor se podrían conseguir también recorridos (por ordenador)? Por ejemplo,en un tablero 100x100.

Se puede. La existencia de solución está probada. Ahora, el problema es difícil hacerlo por ordenador. 100x100 es un tablero muy grande. Al menos el algoritmo que yo conozco usa matrices y como bien sabes manipular una matriz 100x100 es algo difícil. De hecho mi ordenador no puede con matrices tan grandes. Desconozco si existe algún otro algoritmo que te permita resolver el problema con un ordenador normal de los de casa. Pero bueno, con varios ordenadores seguro que se puede sacar.

[FONT=georgia]
dice que no están seguros de que los valores hallados sean correctos. Supongo que esto se ha hecho con ordenadores, como no pueden estar seguros?[/FONT]

Porque los han determinado por ordenador y no usando matemáticas (teoría de grafos, combinatoria...). Vamos, que no lo han calculado sobre el papel (seguramente tengan cotas superiores e inferiores así que lo que deben decir es eso: que no están seguros). Piensa que un ordenador ayuda a orientarnos en un determinado problema pero no podemos hacer demostraciones matemáticas usándolo (véase la historia del teorema de los cuatro colores).