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
JAJAJAJa bueno si creo que tienes razón, aunque ya unos compañeros me comentaron que no habian entendido nada XDXD
supongo que sto es la base para programar un juego de ajedres
cierto?
nunca lo he intentaod , nunca lo he investigado
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
Pingback: Prothotype » Blog Archive » Resumen de las estadisticas de Marzo
no lo puedo hacer!!!!!!!!!!!!!!!!!!!!!!!!!!!
me estoy volbiendo loco
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 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
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, 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
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
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!!!
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 ^^
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
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
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.
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!
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
hey necesito el cdigo ke haga el tablero de ajedrez en funcioness
graciass boeeeeee plisss lo necesito
fetosssss el problema de las reynas tiene 92 soluciones diferentes yo ise un programita para sacar todas las distintas posisiones