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.

Esta entrada fue publicada en General, Programacion, Prozac. Guarda el enlace permanente.

20 respuestas a Las 8 reinas al desnudo

  1. zarzamora dijo:

    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

  2. Prozac dijo:

    JAJAJAJa bueno si creo que tienes razón, aunque ya unos compañeros me comentaron que no habian entendido nada XDXD

  3. FeNtO dijo:

    supongo que sto es la base para programar un juego de ajedres
    cierto?
    nunca lo he intentaod , nunca lo he investigado

  4. Prozac dijo:

    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

  5. Pingback: Prothotype » Blog Archive » Resumen de las estadisticas de Marzo

  6. lucas dijo:

    no lo puedo hacer!!!!!!!!!!!!!!!!!!!!!!!!!!!
    me estoy volbiendo loco

  7. Santiago dijo:

    Hola disculpa sera q me podes enviar el codigo por favor…
    ya lo e intentado y no puedo.. santysos@hotmail.com..
    por favor …
    gracias..

  8. Prozac dijo:

    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

  9. Lisandro dijo:

    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.

  10. Prozac dijo:

    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

  11. dokho dijo:

    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

  12. luis Fernando dijo:

    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!!!

  13. Prozac dijo:

    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 ^^

  14. Luis Fernando dijo:

    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

  15. nelson dijo:

    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

  16. Ali dijo:

    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.

  17. Prozac dijo:

    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!

  18. naza dijo:

    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

  19. innes dijo:

    hey necesito el cdigo ke haga el tablero de ajedrez en funcioness
    graciass boeeeeee plisss lo necesito

  20. daniel dijo:

    fetosssss el problema de las reynas tiene 92 soluciones diferentes yo ise un programita para sacar todas las distintas posisiones

Deja un comentario