Popular channels

[Aporte] Ocho Reinas en C++

Buenas tardes! Quiero compartir con ustedes este código que acabo de hacer, se llama "Ocho Reinas" y se forma a partir del siguiente enunciado: "¿Es posible colocar ocho reinas en un tablero de ajedrez vacío, de tal manera de que ninguna reina ataque a cualquier otra? Es decir, que no haya dos reinas en la misma fila, en la misma columna y a lo largo de la misma diagonal?"

En este ejercicio, usamos, como en el anterior, una heuristica. Pero lo "lindo" de este ejercicio, es que cada vez que se coloca una reina, la heuristica cambia dinamicamente. La heurística nos dice, por cada celda, cuantas posiciones se van a "afectar" (van a estar ocupadas) si pusieramos una reina en esa celda. Explicación más detallada:

Al principio el tablero está vacío:



Entonces, con el tablero vacío, calculamos la heurística (que depende exclusivamente del estado actual del tablero, el cual hasta el momento, esta vacío)



Luego elegimos una posición para la siguiente reina (osea la primera). Cual posición elegimos? La que tenga menos heurística. Por lo tanto se elige cualquiera de las celdas con heurística "21".

Al colocar la reina en la posición {0,0} (con menor heurística "21", el tablero queda de la siguiente manera:



(Los asteriscos indican que esas posiciones están ocupadas y que no pueden ser ocupadas por ninguna reina y se representan internamente mediante booleanos)

Pero oh!! El tablero cambio...entonces la heurística cambia de nuevo...y la siguiente heurística (calculada dinamicamente) es esta:



Teniendo que el menor valor heurística en esta nueva heurística creada dinamicamente es 16...entonces volvemos a elegir una reina y la colocamos en esa posición elegida:



Nuevamente, si cambia el estado del tablero, cambia la heurística, y volvemos a calcular la heurística según el nuevo estado del tablero, y así hasta que el tablero tenga la mayor cantidad posible de reinas que no se ataquen entre sí. (Mi algoritmo logró "7" reinas, pero quiza con una vuelca de tuerca se pudieran llegar a las ocho tal como dice el enunciado)

Sin más los dejo con el código, el cual lo pueden descargar o mirar desde estos links:

http://paste.org/67898
http://www.mediafire.com/?facfkf9te2tqa2t

Un saludo!!
0
0
0
0No comments yet