Algoritmos del Ajedrez por Backtracking

8 dic

El problema del Alfil y el Peón

En un tablero de ajedrez se coloca un alfil en la posición (x,y) y un peón en la posición (1,j), siendo 1<= j <=8. Se quiere encontrar una ruta para que el peón llegue a la fila 8 sin ser comido por el alfil. El único movimiento permitido para el peón es el de avance desde la posición (i,j) a la posición (i+1,j). Si el peón se ve amenazado por el alfil en la posición (i,j), entonces debe retroceder a la fila 1, columna j+1 o j-1. {(1,j+1),(1,j-1)}. Hay que tener en cuenta que el alfil ataca por diagonales. En el siguiente caso por ejemplo, el peón no podría llegar al otro extremo, ya que como se observa en la imagen el alfil controlaria todas las vias de paso:

bishop_move

Recorridos del Rey

Dado un tablero de ajedrez de tamaño nxn, un rey es colocado en una casilla arbitraria de coordenadas (x,y). El problema consiste en determinar los n2–1 movimientos de la figura de forma que todas las casillas del tablero sean visitadas una sola vez, si tal secuencia de movimientos existe.

algebraicnotationonchessboard

El problema de las N – Reinas

El problema de las n reinas se trata de un acertijo en el que se colocan ocho reinas sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848. En el juego de ajedrez la reina amenaza a aquellas fichas que se encuentren en su misma fila, columna o diagonal. Las 8 reinas consiste en colocar sobre un tablero de ajedrez ocho reinas sin que estas se den jaques entre ellas. Para resolver este problema emplearemos un esquema vuelta atrás (o Backtracking).

Dado un tablero de ajedrez de tamaño nxn, este algoritmo es capaz de encontrar todas las formas de colocar n reinas, sin que ninguna de ellas pueda comerse a otra. He implementado tanto la solución iterativa como la versión recursiva del problema, en este caso además la función criterio del problema de las reinas tiene un coste temporal constante y no depende de la talla del problema.

dibujo4

Aquí dejo el código fuente creado por mi y que incluye la solución a los problemas anteriores, así como una optimización del problema de las N – Reinas.

descargar22211

Related Posts Plugin for WordPress, Blogger...


17 Responses to “Algoritmos del Ajedrez por Backtracking”

  1. ivan 12 noviembre, 2010 at 3:39 #

    hola, me podrias ayudar con un juego simple de ajedres que debo realizar para un trabajo, ya que llevo 3 semanas tratando de hacerlo y aun no logro completarlo, el que necesito es uno simple, sin animaciones ni gif ni nada solo que se puedan mover las piezas y listo, de ante mano muchas gracias.

    • Benny De Jesus 18 febrero, 2013 at 14:56 #

      Me Podrias facilitar los codigo en JAVA

  2. Administrador 14 noviembre, 2010 at 12:18 #

    Tengo un ajedrez en C# hecho por mi, dime en que lenguaje lo necesitas e intentaremos poner un articulo. un salu2

  3. Alejandro 18 diciembre, 2010 at 16:26 #

    Me podrias pasar el juego de ajedrez en c#

  4. Alejandro 18 diciembre, 2010 at 16:27 #

    Necesito presentarlo para una materia… Gracias

  5. Administrador 19 diciembre, 2010 at 10:39 #

    Alejando pulsa en descargar y tendrás el código fuente

  6. Alejandro 27 diciembre, 2010 at 14:22 #

    Muchisimas gracias por el aporte me sirvio de mucho :) sigue asi….

  7. Alejandro 27 diciembre, 2010 at 14:22 #

    Y felicies fiestas ;) todo lo mejor

  8. Administrador 28 diciembre, 2010 at 0:37 #

    Igualmente Alejando, me alegro que te sirviera de utilidad

  9. mafer 30 marzo, 2012 at 17:06 #

    hola necesito hacer un Algoritmos del Ajedrez por Backtracking en recursiva en java por favor ayudame

  10. david 26 junio, 2012 at 17:27 #

    HOla no puedo descargar el codigo del juego de ajedrezz

  11. david 26 junio, 2012 at 17:28 #

    a ver si podrian subir el codigo en otra pagina ya que megaupload lo cerraron

  12. Alexei 12 julio, 2012 at 15:01 #

    Hola
    Estoy desarrollando un juego de ajedrez en C++, usando Qt como biblioteca gráfica. En estos momentos sólo me falta, en cuanto a los movimientos de las piezas, reconocer el jaque, jaque mate, enroques y el peón al paso. En cuanto logre esto, voy a hacer lo de jugar en red, porque realmente lo que quiero es que se pueda jugar en red LAN con mi juego, ya que existen muchos juegos buenos de escritorio en las distribuciones de GNU/Linux, pero no he visto uno que permita jugar en red.
    Ahora necesito ayuda con los mov antes mencionados…si alguien tiene algo adelantado y puede ayudarme, le estaría agradecido, así ahorro tiempo de desarrollo.
    Gracias de antemano.
    Salu2

    • Iván 4 julio, 2013 at 6:06 #

      Hola Alexei,

      Disculpa, tengo que hacer el mismo juevo en c++ usando backtracking, lo necesito para una asignatura de mi carrera, por favor me puedes ayudar??? muchas gracias.

  13. kefff 19 junio, 2013 at 23:43 #

    la descarga no sirve

  14. sergio 2 julio, 2013 at 21:43 #

    hola espero que estes bien me gustaria tener los codigos pero no puedo descargarlos no funciona el boton de descarga ojala ma respondas a mi correo cuidate un abrazo y gracias

  15. Jhon 25 noviembre, 2013 at 16:44 #

    Hola no sirve el botón descarga

Leave a Reply