Abr 29

El problema del caballo de ajedrez

Caballo de ajedrezEl sitio Alquimia, Entre Utopía y Libertad querido lector, siempre ha tratado de abordar temas interesantes, educativos, constructivos y que sirvan para la vida en general de las personas.

Aunque pueda parecer que este articulo no tenga puntos en común con la descripción anterior y sea un poco difícil y abstracto su entendimiento, tratare de hacerlo lo mas terrenal posible, para que mis lectores puedan entender lo que quiero expresar, y se lleven una idea que aporte en sus vidas y tal vez sea la llave a un tipo de pensamiento y métodos de resolver problemas prácticos que tal vez para unos siempre existieron y no sabían como describirlos y para otros es una practica novedosa y útil para incorporar a la vida.

El problema del caballo de Ajedrez es uno de los ejercicios que se dan en la Asignatura: Análisis y Diseño de Algoritmos de las carreras de Ciencia de la Computación e Ingeniería en Informática, aunque creo que el conocer como se resuelve dicho problema es algo que enriquece nuestro pensamiento y puede ser conocido por lo menos la parte que pretendo exponerle a Uds. por nuestros educandos que cursan el nivel del Pre-Universitario y enriquecer la cultura de curiosos problemas con sus soluciones.

El problema es bastante curioso y dice así:

Se tiene un tablero de Ajedrez (en realidad puede ser un tablero cualquiera,lo que en nuestro caso exigiremos que sea cuadrado o sea (nxn)) y se sitúa un caballo solitario en cualquier casilla de este y se quiere que utilizando los movimientos de ajedrez de este, el caballo recorra todas las casillas del tablero sin repetir ninguna casilla visitada

Para la resolución de este problema, primero debemos hablar de métodos o filosofías de resolución de problemas prácticos que es necesario que el lector asimile y conozca para que pueda entender como se resuelve nuestro problema del caballo de ajedrez.

Para esto es necesario que nuestro lector para una mejor comprensión de lo que se va a exponer mas adelante lea la primera parte del articulo publicado hace ya bastante tiempo en nuestro blog llamado: El pensamiento Algorítmico

Su Url es: http://maverick.cubava.cu/2014/12/11/el-pensamiento-algoritmico/

Tal vez este artículo que ahora estamos leyendo sea leído por colegas especialistas. Quiero expresar que para que el artículo pueda ser entendido, he tratado de no ser tan riguroso con el lenguaje técnico, omitiendo algunos detalles y sustituyendo por símiles algunas definiciones para que la mayoría de las personas que lo lean puedan entender. Si es así pido disculpas ante la comunidad de especialistas de nuestra ciencia.

 

 METODOS DE RESOLUCION DE PROBLEMAS

LOS ALGORITMOS AVIDOS.

Si alguien que no es entendido de nuestra ciencia busca un libro que tenga que ver con el Análisis y Diseño de Algoritmos en el capitulo de los algoritmos ávidos y ve la definición de estos se le hará complejo el entenderlo por lo tanto tratare que con estas palabras lo logre.

Básicamente la técnica de los Algoritmos ávidos esta en seleccionar y analizar en los diferentes puntos de la solución en los que se esta los candidatos que puedan ser solución parcial del problema, tomando en ese punto la mejor variante, incorporar el candidato a la solución y desechar ese candidato en las próximas elecciones de candidatos del futuro, pasando a un nuevo punto de la resolución del problema.

Vamos a aterrizar esta definición con dos problemas descritos para que Ud. querido lector pueda entender que es lo que trato de decirle.

EL PROBLEMA DEL CARTERO.

A un cartero se le da la tarea de repartir la correspondencia entre ciudades en una bicicleta. Como requiere de esfuerzo físico, el cartero tiene que visitar cada ciudad y quiere hacerlo con el menor esfuerzo, o sea recorriendo la menor distancia posible hasta que haya visitado todas las ciudades. Como requerimiento indispensable se sabe que de cada ciudad en el mapa se puede viajar a cualquier ciudad restante, o sea que hay carreteras que comunican a todas las ciudades entre si.

Por supuesto en dicho mapa están las distancias de recorrido de cada carretera de una ciudad a todas las demás.

La solución mediante la técnica Ávida seria la siguiente:

El cartero por supuesto parte de una ciudad determinada y quiere resolver su problema con el menor esfuerzo posible.

Los candidatos a elegir en este caso serian las ciudades que aun no se han visitado, por lo tanto el cartero siguiendo la técnica Ávida, ira hacia la ciudad que le quede mas cerca en ese momento y que no haya sido visitada y marcara como ciudad visitada en la que esta, no pudiendo retornar mas a esta, y así ira visitando las ciudades siguiendo esta filosofía y marcando las ciudades visitadas hasta que las visite todas.

EL PROBLEMA DEL CAMBIO

Se quiere dar un vuelto producto de una compra y se quiere hacer con la menor cantidad de monedas posibles.

Para este caso se hará un listado del sistema Monetario en el que se trabaja, describiendo las monedas con sus valores.

Si utilizamos nuestro sistema monetario en Cuba, y buscamos un vuelto de monedas menores a un peso podemos describir las monedas con sus valores como:

  • Monedas de un centavo (este tipo de monedas es fundamental para que pueda darse un vuelto completo)
  • Monedas de 5 centavos
  • Monedas de 20 centavos

La solución en este caso por la técnica Ávida seria la siguiente:

Los candidatos en este caso seria que tipo de monedas utilizaríamos en cada caso.

El problema radica en cuantas de ellas elegir en cada momento para irlas agregando como solución parcial del problema hasta que se haya dado un vuelto correcto

Un análisis no profundo le da al ser humano corriente que para dar un cambio con la menor cantidad de monedas, es necesario irlo dando partiendo de las monedas con valores mayores hasta las monedas con valores menores (o sea hay que organizar decrecientemente las monedas por su valor, e ir amortizando el vuelto dado utilizando de mayor a menor las monedas), contar la cantidad de estas, multiplicar esta cantidad por su valor y mientras la resta de el vuelto que se necesita dar en el momento con este valor obtenido sea mayor o igual que cero se obtendra un nuevo vuelto a buscar, ya que parte del vuelto que estamos buscando lo estamos efectuando cada vez que incertamos una moneda valida. Se contaran las cantidades de monedas elegidas en ese punto y marcaremos como candidato inutilizable a las monedas de ese valor una vez que ya no se pueda dar mas vuelto con estas, ya que el vuelto restante por dar es menor que el tipo de monedas que estamos utilizando, pasando el problema a otra fase, ahora con el tipo de monedas restantes en el orden decreciente de eleccion, pues se sabe que el vuelto que falta por dar ya no se puede dar con las monedas anteriores, así sucesivamente hasta llegar a dar el vuelto completamente.

Vamos a ver un ejemplo práctico para que puedan entender el problema:

Ejemplo 1:

Se quiere dar un vuelto a un usuario de 13 centavos.

  1. Organizamos las monedas decrecientemente o sea (las monedas de 20, las monedas de 5, las monedas de 1 centavos respectivamente)
  2. Elegimos las monedas de 20 centavos (eleccion de candidatos)
  3. Restamos 13-20 y vemos que el numero da negativo, o sea para dar un vuelto de 13 centavos es imposible hacerlo con monedas de 20 centavos por lo tanto agregamos al Conjunto Solución S las cantidades de las monedas obtenidas que estas coinciden como sucesión al sistema Monetario o sea tenemos que S={0(cantidad de monedas de 20 centavos)}
  4. Marcamos como inutilizables para el vuelto  a las monedas de 20 centavos (desechar candidato).                El vuelto a dar se mantiene en 13 centavos.
  5. Elegimos ahora las monedas de 5 centavos (eleccion de un nuevo candidato).
  6. Tomamos una moneda de 5 centavos, restamos 13-5 = 8, vemos que aun hay vuelto por dar, agregamos al conjunto solución S ahora:                                                                                                                                                 S= {0 (monedas de 20 centavos) ,1(monedas de 5 centavos)}.                                                                                    El vuelto ahora a dar es 8 centavos pues ya agregamos una moneda de 5 centavos a nuestra solución.
  7. Tomamos otra moneda de 5 centavos
  8. Restamos 8 (el vuelto que falta por dar)-5=3, es positivo el resultado, aun falta resto por dar, agregamos al conjunto solución S ahora:                                                                                                                                                S= {0 (monedas de 20 centavos) ,2(monedas de 5 centavos)}.                                                                                    El vuelto ahora a dar es 3 centavos pues ya agregamos una moneda de 5 centavos a nuestra solución.
  9. Tomamos otra moneda de 5 centavos
  10. Restamos 3-5, da negativo, o sea ya no se puede dar mas vueltos con monedas de 5 centavos.
  11. Marcamos como inutilizables para el vuelto  ahora a las monedas de 5 centavos (desechar candidato). El vuelto a dar se mantiene en 3 centavos.
  12. Tomamos ahora las monedas de 1 centavo (eleccion de un nuevo candidato)
  13. Restamos 3 (el vuelto que falta por dar)-1=2, es positivo el resultado, aun falta resto por dar, agregamos al conjunto solución S ahora:                                                                                                                                                     S= {0 (monedas de 20 centavos) ,2(monedas de 5 centavos) ,1(monedas de un centavo)}.                                 El nuevo vuelto ahora a dar es 2 centavos pues ya agregamos una moneda de 1 centavos a nuestra solución
  14. Tomamos otra moneda de 1 centavo
  15. Restamos 2 (el vuelto que falta por dar)-1=1, es positivo el resultado, aun falta resto por dar, agregamos al conjunto solución S ahora:                                                                                                                                                S= {0 (monedas de 20 centavos) ,2(monedas de 5 centavos) ,2(monedas de un centavo)}.                                 El nuevo vuelto ahora a dar es 1 centavos pues ya agregamos una moneda de 1 centavos a nuestra solución.
  16. Tomamos otra moneda de 1 centavo
  17. Restamos 1 (el vuelto que falta por dar)-1=0, es el vuelto deseado, agregamos al conjunto solución S ahora:                                                                                                                                                                                     S= {0 (monedas de 20 centavos) ,2(monedas de 5 centavos) ,3(monedas de un centavo)}.                                 El vuelto a dar es cero
  18. Fin del proceso.

Vemos que nuestro conjunto Solución es:

S= {0, 2,3}

O sea que para dar un vuelto de 13 centavos con nuestro sistema Monetario lo hacemos:

Con ninguna moneda de 20 centavos, con dos monedas de 5 centavos y con tres monedas de un centavo, o sea damos un vuelto con 5 monedas.

 

REPERCUSION PRACTICA DE USAR LOS ALGORITMOS AVIDOS

De este esquema se desprende que los algoritmos ávidos son muy fáciles de implementar y producen soluciones muy eficientes.

Entonces cabe preguntarse: por qué no utilizarlos siempre????????

En primer lugar, porque no todos los problemas en general a que nos enfrentamos admiten esta estrategia de solución.

De hecho, la búsqueda de óptimos locales no tiene por qué conducir siempre a un óptimo global. La estrategia de los algoritmos ávidos consiste en tratar de ganar todas las batallas sin pensar que, como bien saben los estrategas militares y los jugadores de ajedrez, para ganar la guerra muchas veces es necesario perder alguna batalla.
Desgraciadamente, y como en la vida misma, pocos hechos hay para los que podamos afirmar sin miedo a equivocarnos que lo que parece bueno para hoy siempre es bueno para el futuro.

Y aquí radica la dificultad fundamental de utilizacion en la vida practica de estos algoritmos:
Encontrar el método de selección que nos garantice que el candidato escogido o rechazado en un momento determinado es el que ha de formar parte o no de la solución óptima sin posibilidad de reconsiderar dicha decisión.

Por ello, una parte muy importante de este tipo de algoritmos es la demostración formal de que el método de selección escogido consigue encontrar óptimos globales para cualquier situación practica. No basta con diseñar un procedimiento ávido, que seguro debido a su eficiencia, este tipo de algoritmos es muchas veces utilizado aun en los casos donde se sabe que no necesariamente encuentran la solución óptima.

En algunas ocasiones la situación nos obliga a encontrar pronto una solución razonablemente buena, aunque no sea la óptima, puesto que si la solución óptima se consigue demasiado tarde, ya no vale para nada (piénsese en el localizador de un avión de combate, o en los procesos de toma de decisiones de una central nuclear).
Es decir, la eficiencia de este tipo de algoritmos hace que se utilicen aunque no consigan resolver el
problema de optimización planteado, sino que sólo den una solución “aproximada”.
El nombre de algoritmos ávidos, también conocidos como voraces (su nombre original proviene del término inglés greedy) se debe a su comportamiento: en cada etapa “toman lo que pueden” sin analizar consecuencias, es decir, son glotones por naturaleza.1

Vamos a traducir al lenguaje natural estas definiciones iendo ahora a los problemas que hemos descrito anteriormente

El problema del Cartero:

Como hemos descrito anteriormente, el cartero va viajando de ciudad en ciudad, marcando las ciudades visitadas y escogiendo la próxima ciudad atendiendo a la menor distancia en ese punto a recorrer. Esto puede no ser la ruta mas optima, pues el ir escogiendo la distancia menor en cada punto visitado, tal vez utilizando otra ciudad que no clasifica como ciudad ubicada a la menor distancia del punto, puede haber una configuración de mapas en que siguiendo esta filosofía recorra óptimamente el objetivo trazado pues tal vez arriesgando un poco en un punto determinado o en varios puntos la ciudad a escoger debido a su distancia, el pueda recorrer todas con un esfuerzo menor que el seguido por una filosofía avida2.

El problema del Cambio:

Como este problema lo definimos en un lenguaje algorítmico natural pondremos un ejemplo en el que siguiendo la filosofía ávida no se da la solución óptima:

Ejemplo 2:

Imaginemos que tenemos el siguiente sistema Monetario:

  • Monedas de 12 centavos
  • Monedas de 5 centavos
  • Monedas de 1 centavo

Se quiere dar un vuelto de 15 centavos

Aplicando el algoritmo antes descrito el conjunto solución del problema seria:

S= {1(monedas de 12 centavos) ,3 (monedas de 1 centavo)}

Damos en ese caso un vuelto con 4 monedas.

Vemos que la aplicación del algoritmo ávido en este caso particular no dio la solución óptima, pues esta seria:

S= {3(monedas de 5 centavos)}

O sea dar un vuelto con solo 3 monedas.

Ahí esta el problema de los algoritmos ávidos, al ser muy glotones y avanzar por la mejor solución optima local, arriesgan mucho en dar la solución optima global, es por eso que el utilizar este tipo de algoritmos esta muy condicionado por el problema y su configuración inicial, la elección de los candidatos, la forma y el orden de elegirlos y la forma de desecharlos.

Estamos preparados ahora para analizar nuestro problema en cuestión: El problema del caballo de ajedrez

EL PROBLEMA DEL CABALLO DE AJEDREZ.

Figura 1: Movimientos posibles de un caballo de ajedrez en un tablero

Figura 1: Movimientos posibles de un caballo de ajedrez en un tablero

Vamos a definir que el caballo de ajedrez es una pieza solitaria que se pondrá en un tablero cualquiera, no necesariamente tiene que ser de ajedrez (8×8), lo que si para su mejor comprensión necesariamente el tablero debe ser cuadrado (nxn).

Dada una posición de partida inicial del caballo (x0[numero de la fila]),y0[numero de la columna]) queremos que este recorra todo el tablero sin repetir casillas visitadas.

En este caso los candidatos a elegir son las casillas no visitadas, definiremos entonces cual seria la forma de elección de candidatos.

La forma en que se resuelve la toma de decisión de los candidatos en el tablero para resolver el problema del caballo de ajedrez y que este pueda recorrer todas las casillas del tablero sin repetir ninguna es tratar de elegir la casilla no visitada en la cual a partir de ahí el caballo de ajedrez tenga menos posibilidades de moverse en el próximo paso

Fíjese el lector que difícil es tratar de escoger esta función de definición de los candidatos posibles y el encontrar esta idea no es muy sencilla.

Para eso primero debemos tener claramente como puede moverse un caballo de ajedrez en un tablero y definir sus movimientos.

Si observamos la figura 1 y enumeramos, definimos y ordenamos los movimientos del caballo de ajedrez partiendo de 1 hasta 8 posibles movimientos, tomando el primer movimiento como el superior mas a la izquierda y siguiendo un sentido horario tenemos que los 8 movimientos del caballo de ajedrez desde una posición ( x k,y m) de un tablero cuadrado hacia una posición( x k+1,y m+1) , convirtiendo el propio tablero en un sistema de coordenadas cartesianas, las definiriamos de la siguiente forma:

  • posición 1: se le restan 2 posiciones a la x y se le suma una 1posicion a la y
  • posición 2: se le resta 1 a la x y se le suman 2 a la y
  • posición 3: se le suma 1 a la x y se le suman 2 a la y
  • posición 4: se le suman 2 a la x y se le suma 1 a la y
  • posición 5: se le suman 2 a la x y se le resta 1 a la y
  • posición 6: se le suma 1 a la x y se le restan 2 a la y
  • posición 7: se le resta 1 a la x y se le restan 2 a la y
  • posición 8: se le restan 2 a la x y se le resta 1 a la y

Por supuesto hay que aclarar que cada movimiento es valido si y solo si el movimiento esta dentro del tablero, pues cuando el caballo esta situado cerca de los bordes , hay movimientos de este que no pueden efectuarse porque caerían fuera del tablero.

Deberíamos elegir ahora la forma en que se irán probando las casillas de candidatos, contando por supuesto que a partir de esa casilla el caballo tuviese la menor posibilidad de movimiento en el proximo paso hacia una casilla no visitada. Si por alguna casualidad hubiesen casillas con igual numero de menores posibilidades de movimiento en el futuro y por supuesto estas casillas son candidatos (o sea casillas no visitadas), escogeríamos de entre todas con iguales probabilidades de menor movimiento la primera en aparecer, nos moveríamos hacia esta marcando antes la casilla abandonada como visitada, repitiéndose el proceso hasta que haya visitado todas.

La idea básica del problema es tratar de que el caballo de ajedrez  ” tienda a arrinconarse hacia las puntas del tablero” primeramente, tratando de visitar todas las puntas del tablero en una etapa inicial y después describiría o tiende a describir una espiral que se va cerrando hacia el centro del tablero hasta que no se pueda mover mas (pues todas las casillas a partir de la posicion en que esta con sus 8 posibles movimientos han sido visitadas).

Como algoritmo ávido al fin, esta forma de solucionar el problema del caballo de ajedrez tiene puntos vulnerables o configuraciones iniciales de arranque que no permiten que el caballo de ajedrez pueda visitar todas las casillas del tablero.

Definiremos la filosofia avida para todos los casos de la siguiente forma:

  • El tablero cuadrado debe ser mayor a dimensiones de 4×4. El lector puede experimentar tableros menores o iguales que este número y vera que habra situaciones en que no se pueden recorrer todas las casillas, precisamente por la forma de moverse del caballo de ajedrez.
  • Para dimensiones de nxn con n > 4 y n par, el problema del caballo de ajedrez aplicando este algoritmo ávido tendrá siempre solución.
  • Para dimensiones nxn con n > 4, n impar, el problema tiene solución para aquellas casillas iníciales de arranque del caballo (x0,y0) que verifiquen que x0 + y0 sea par.

Pero observemos que el algoritmo implementado no ha encontrado solución en todas estas situaciones. Por ejemplo:

Para n = 5, y posición de arranque del caballo de ajedrez  x0 = 5 e y0 = 3 el programa dice que no la hay.

Sin embargo, sí la encuentra para :

  • n = 5, y posición de arranque x0 = 1 e y0 = 3
  • n = 5, posición de arranque del caballo x0= 3 e y0 = 1
  • n = 5,posicion de arranque del caballo  x0 = 3 e y0= 5

Estos tres casos de arranque son simetricos del caso en que no puede recorrer el tablero completo.

La logica dice que de existir solución para alguno de ellos, por simetría se obtiene para los otros. ¿Por qué no la encuentra nuestro algoritmo?

La respuesta a esta pregunta se encuentra en cómo buscamos la siguiente casilla a donde saltar. Por la forma en la que funciona el algoritmo, siempre probamos las ocho casillas y escojemos la primera menor probabilidad de movimiento en el futuro en el sentido de las agujas del reloj. Ahi esta su talon de Aquiles!!!!!!!!

Esto hace que nuestro algoritmo no sea simétrico.

En resumen, estamos ante un algoritmo ávido que no funciona para todos los casos.

CONCLUSIONES

 Espero que haya sido de su agrado querido lector este articulo y haya aprendido que muchas formas en la que soluciona problemas en su vida diaria tal vez sea mediante algoritmos ávidos, solo que tal vez no había tenido la oportunidad de definirlos como lo hemos hecho aquí, espero que pueda probar con calma si le ataca la curiosidad el problema del caballo de ajedrez y vea realmente la trayectoria que describe, no tanto así sus casos particulares de fallos, aunque si es lo suficientemente curioso y perseverante lo invito a que lo haga.

Hay muchas veces que el pensamiento de las personas esta reflejado mecánicamente como un pensamiento Ávido (glotón), cuando están en una toma de decisiones siempre se van por la vía mas rápida, o la aparentemente vía mas corta en ese momento, y en el futuro se dan cuenta que las decisiones tomadas no fueron las correctas.

El Analisis y Diseño de Algoritmos, como muchas asignaturas de estas carreras de ciencias no solo sirven para darnos herramientas de modelacion matematica para efectuar programas de computadoras eficases sino que nos moldean para siempre nuestras vidas a las personas que nos graduamos en ellas. Pareceria que somos extraterrestres pero no………………………. somos tan mortales como Ud, querido lector.

Tal vez este articulo querido lector sea su incentivo para estudiar a fondo como podra pensar mejor en el futuro y como trazar sus extrategias futuras para la vida, se lo recomiendo……………………..es una buena practica.

De tarea para los que hayan llegado a esta parte del articulo sin aburrirse y entendiendo todo lo que he tratado de explicarles lo mas terrenalmente posible le dejo un problemita de tableros de ajedrez que su solución esta vez no es aplicando los algoritmos ávidos, pero si puede ser algo curioso que posea en casa para desarrollar el pensamiento algorítmico y tal ves su solución sea la musa inspiradora a otro articulo, esta vez tratando de explicarles otro tipo de Técnicas de Análisis y Diseño de Algoritmos.

El problema de las damas de ajedrez

Se tiene un tablero de ajedrez (8×8) y se quieren poner 8 damas de ajedrez en el de tal forma que ninguna se ataque.

Que lo disfruten………………………………………………

Lic. Richard Matos Rodriguez

E-mail: rmatos@stgolub.cubalub.cupet.cu

Leyenda:

1 Tomado del Libro: Técnicas de Diseño de algoritmos. Segunda Edición, Universidad de Málaga, 1999, Algoritmos Ávidos, pp. 142-143.

2 Como todo el mundo puede interpretar de estos algoritmos, el juego de ajedrez no puede ser resuelto mediante una técnica de Algoritmos Ávidos, pues a veces en una jugada es necesario sacrificar piezas o no eliminar en una jugada una pieza del contrario aparentemente indefensa (o tal vez un posible cebo que nos ha tendido el contrario) para dar el Jaque Mate final.

 

 

1 comentario

    • Jose on 30 abril, 2015 at 6:44 pm
    • Responder

    Me gustó mucho el artículo. Quisiera si es posible, tratara en algún momento sobre el Juego de Dominó.

Deja un comentario

Your email address will not be published.