Las 8 reinas al desnudo
Jaja si quedo como extraño el nombre del post, pero bueno así me indexa google bajo reinas desnudas XD. No no voy a colocar pr0n, es el algoritmo de las 8 reinas al que me refiero, si ese con el que aprendiste backtracking, el mismo.
Hoy vamos a ver como resolver el algoritmo de una manera óptima, bajando el orden del mismo, veamos.
Planteamiento del problema
Colocar 8 reinas en un tablero de ajedrez(8×8) de manera tal que ninguna de ellas amenace a ninguna de las demás. Una reina amenaza a los cuadrados de la misma fila, de la misma columna y de las mismas diagonales.
Solución
Primero olviden todo lo que saben de este problema(si desde un principio no sabias nada mejor XD) bien.
Suponga que el vector V = [v1,v2,v3,v4,v5,v6,v7,v8] representa las posiciones de ocho reinas en un tablero de ajedrez, con una reina en cada columna, es decir:
Si V[i] = vj ( 1 = i,j = 8 ) entonces la reina colocada en la columna i esta en la fila vj.
Si V[i] = 0 ( 1 = i = 8 ) entonces todavía no se ha colocado una reina en la columna i.
Traducción
Primero modelamos el tablero de ajedrez como un vector V de 8 posiciones, donde cada posición del vector representa la coordenada “j” donde esta colocada la reina, y el valor del vector en x posición sera la coordenada “i”, es decir si una reina va en las coordenadas 2,4 entonces nuestro vector V[4]=2, sabemos que solo ira una reina por columna y por fila del tablero así que podemos hacer esta gracia.
De esta manera nos ahorramos la validación de la amenaza por columnas, ahora debemos verificar por filas, y en diagonal.
Para validar la amenaza por filas solo tenemos que asegurar que no se repita ningún valor dentro del vector ya sea que los asignemos lineal(un ciclo for o algo) o aleatorio sin repetición, y de esta manera aseguramos esta condición, ahora solo queda una, la amenaza diagonal, que es la mas linda.
Fijense, como sabemos que 2 reinas(digamos Wi,j y Zx,y) están en la misma diagonal?
ya validamos la amenaza de filas y columnas, y al validar que los valores del vector sean distintos al del índice en esa posición no sean iguales validaríamos la diagonal principal, es decir V[2]== 2 no debe suceder, además de esto también debemos validar las otras diagonales, esto se hace y de la siguiente manera la resta de las coordenadas debe ser distinta, por ejemplo, recuerdan a Wi,j y Zx,y bueno la condición seria asi |i-x!|!=|j-y|, llevado a nuestro problema quedaría que, tomando V[3]=2 y V[7]=6 se amenazan porque están en la misma diagonal, y se valida restando 6-2 que es 4 y 3-7 que es 4(en valor absoluto por supuesto)
Formalmente
V = {[v1,v2,v3,v4,v5,v6,v7,v8] :
para todo i,j : 1 < = i,j <= 8 : (1 <= vi <= 8)&&(i != j -> vi != vj)&&(|vi-vj| != |i-j|)}
Extra
Juego en flash de las 8 reinas.
Les debo el código implementado no he tenido mucho tiempo estos días.
wow!!! por Dios!!! eso me recordó que cuando tenía como 8 años me inscribieron en un curso de ajedréz muy didáctico y me pusieron ese mismo problema, sólo que lo resolvimos de otra manera, es decir, como le dices a un niño de 8 años todo lo que tu le acabas de decir sin que salga corriendo, nah!! era más divertido pensar en que aquí se la come, aquí no… XD
zarzamora - Febrero 14th, 2006 at 12:37 am
JAJAJAJa bueno si creo que tienes razón, aunque ya unos compañeros me comentaron que no habian entendido nada XDXD
Prozac - Febrero 14th, 2006 at 10:23 pm
supongo que sto es la base para programar un juego de ajedres
cierto?
nunca lo he intentaod , nunca lo he investigado
FeNtO - Febrero 18th, 2006 at 4:37 pm
No fento, aunque si aplica, pero en realidad es un ejercicio tipico, como las torres de Hanoi, o no se, el calculo del factorial recursivo, o fibonacci.
pero esta solución es muy “alternativa” jajajaja
Prozac - Febrero 18th, 2006 at 5:32 pm
[…] La gente ha llegado a prothotype buscando gran variedad de cosas, muchos llegaron buscando algún capitulo de la serie Bunny Kill, también llego gente interesada en la galeria PHP con Thumbnails, o como recorrer un directorio en PHP, también llegaron buscando invitaciones al Windows Live Messenger, buscando fotos de Cuyagua (playa en Venezuela), o vídeos de apocalyptica (que están disponibles de nuevo), algunos buscando la solución al problema de las 8 reinas y precisamente a partir de ese post de las ocho reinas, llego también gente buscando las reinas del desnudo […]
Prothotype » Blog Archive » Resumen de las estadisticas de Marzo - Abril 3rd, 2006 at 9:44 am
no lo puedo hacer!!!!!!!!!!!!!!!!!!!!!!!!!!!
me estoy volbiendo loco
lucas - Julio 2nd, 2006 at 5:05 pm
Hola disculpa sera q me podes enviar el codigo por favor…
ya lo e intentado y no puedo.. santysos@hotmail.com..
por favor …
gracias..
Santiago - Julio 14th, 2006 at 6:22 pm
Santiago la otra manera que puedes resolver el problema es que posiciones las reinas con movimientos de caballo entre una y otra, y asi sale mas facil
Saludos
Prozac - Julio 19th, 2006 at 5:37 pm
Hola aunque crean q estoy medio loco, recien me inicio en el mundo de la programacion de c++, action script y basic, y como me parecia demaciado complejo, pq no se como hacer q el programa me resuelva solo todas las posibilidades (esto lo realizo un conocido y no me quiere dar el algoritmo) lo resolvi con lapiz y papel y obtuve 12 soluciones, quisiera saber si es posible encontrar mas.
Lisandro - Octubre 16th, 2006 at 9:48 am
Lisandro, si lo que quieres saber es la cantidad de soluciones posibles hay una formula para ello, no recuerdo muy bien cual es, hace tiempo que no hago nada con el problema de las reinas, pero en realidad, depende del tamaño del tablero, me explico, este es un problema conocido como las N-reinas, si lo aplicas a un tablero de ajedrez como lo conocemos seria las 8 reinas(como dice el titulo del post) pero el problema es mas complejo (con el tamaño del tablero N) y para cada N hay una cantidad de soluciones bastante grande (aumenta exponencialmente) creo que 12 soluciones tiene el tablero de 4, porque cuando consigues una solución esa solución tiene “espejos” es decir una solución se convierte en otra “distinta” si rotas el tablero sobre su eje XD XD ok esto es medio enredado
La cosa es que hay una formula para saber la cantidad de soluciones para un tablero de N posiciones, solo tienes que usar la fuerza
Prozac - Octubre 16th, 2006 at 9:58 am
hola es muy buena respuesta ya que no se me habia ocurrido por cierto existe la posibilidad de que sea implementado en lisp? de ser asi por favor dime como ya que es algo todavia no sale, peor lo intentare en estos dias
dokho - Febrero 2nd, 2007 at 5:13 pm
Hola, esta interezante esa solucion, pero si me pueden ayudar con esto seran mis heroes, necesito una solucion recursiva que sea capaz de calcular las 96 soluciones posibles para un tablero de 8×8,alguna idea?, como si fuera poco ocupo implementarlo en lenguaje Caml para linux, pero es otro historia, por favor si alguien me puede ayudar contactarme al siguiente correo: lsequeiral@gmail.com
Gracias!!!
luis Fernando - Marzo 6th, 2007 at 7:51 pm
dokho, la verdad no tengo mucha idea de lisp, pero es muy posible que si se pueda
Luis F, lo que tienes es que buscar acerca de backtracking esa es la manera de solucionar un problema donde se plantean encontrar todas las soluciones ^^
Prozac - Marzo 7th, 2007 at 7:10 pm
Si claro es la solucion mas obvia pero si estuviese con prolog seria genial, pero resulta ser que ML no se presta para esos trabajos. Pero muchas gracias de todas formas
Luis Fernando - Marzo 7th, 2007 at 7:22 pm
hola necesito ayuda sobre este problema de las 8 reinas debo hacerlo en c++ , me podrias ayudar con este codigo? lo que debo hacer es ingresar por teclado una cantidad N de Reinas en un Tablero de N*N sin que ninguna de ellas se ataque. eso muchas gracias ojala reciba respuesta tuia por favor
nelson - Junio 13th, 2007 at 2:29 am
Buenas, yo estoy igual que nelson, es para unas practicas que tengo que entregar en verano, y me ha cogido el toro, como se suele decir, si alguien me puede dar alguna idea se lo agradeceria mucho. un saludo.
Ali - Septiembre 1st, 2007 at 7:12 am
Lo siento gente pero no creo que los ayude si les doy el codigo, eso seria hacer la tarea por uds, vamos codifiquenlo que no es tan dificil! uds pueden! lean el post con detenimiento y seguro que practicando un poco logran calcular las soluciones!
Prozac - Septiembre 1st, 2007 at 1:40 pm
hola con que tecnica lo hicistes me imagino que con backytraking no por que con 100000 reinas t va a tardar un poquito en compilar, t agradeceria ssi serias mas especifico
gracias
naza - Octubre 8th, 2007 at 11:49 am
hey necesito el cdigo ke haga el tablero de ajedrez en funcioness
graciass boeeeeee plisss lo necesito
innes - Noviembre 23rd, 2007 at 6:46 pm