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:
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.
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.
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.
