Implementación del problema de las N-Reinas en Prolog (programación lógica)

Una implementación sencilla del problema de las n-reinas en Prolog consiste en tres simples pasos:

  1. Generar un tablero de dimensión n.
  2. Generar una permutación sobre ese tablero.
  3. Comprobar si ese tablero cumple la condición de que todas las reinas colocadas no se amenacen entre sí.

Gracias al backtracking de Prolog podemos volver a preguntar por un resultado cuando nos muestra una solución, y así poder generar todas las posibles soluciones.

Implementación

nreinas (+N,?Sol). El primer predicado y el cual llamamos desde el intérprete de Prolog . Se satisface si Sol es la solución al problema de las N-Reinas en un tablero de tamaño N.

nreinas(N,Sol):- generarTablero(N,Tablero),
permutar(Tablero,Sol),
buenTablero(Sol).

Este predicado generar un tablero de dimensión N, generar una permutación de ese tablero y por último comprueba si esa permutación contiene reinas es posiciones que no se amenacen unas a otras.

generarTablero(+X,?Y). se verifica si Y es una lista de X elementos que contiene los naturales comprendidos entre 1 y X, ambos inclusive. Nótese que:

  • Como cada reina habrá de ocupar una columna distinta, el tablero (o tableros) solución será (serán) una permutación de un tablero así generado.

generarTablero(0,[]).
generarTablero(X,[X|R]):-
XMenos1 is X - 1,
XMenos1 >= 0,
generarTablero(XMenos1,R).

Este predicado genera un tablero de la forma [N,N-1,N-2,….,1].

permutar(?LX,?LY). se verifica si LY es una permutación de los elementos de LX, la única permutación de la lista vacía es la lista vacía.

permutar([],[]).
permutar(X,[C|Z]) :- seleccionar(X,C,R), permutar(R,Z).

Para realizar la permutación de la lista de entrada, se seleccióna el primer valore de la lista y se permuta con el resto de la lista.

seleccionar(L,X,R). se verifica si X es un elemento de L y R es la lista L sin el elemento X.

seleccionar([X|R],X,R).
seleccionar([C|R],X,[C|Y]) :- seleccionar(R,X,Y).

buenTablero(+X). se verifica si en el tablero X, ninguna reina amenaza a otra. Hay que tener en cuenta que:

  • Amenazar es una relación simétrica, es decir, lo mismo da amenazar que ser amenazada.
  • Lo que se ha llamado Tablero es una lista de n elementos con los naturales de 1 a n donde cada elemento especifica la columna que ocupa la reina en el tablero, y la fila se especifica por el orden del elemento en la lista. (En resumidas cuentas, acorde a las especificaciones de la práctica).

buenTablero([]).
buenTablero([C|R]):- not(amenaza(C,R)),
buenTablero(R).

Se comprueba que la reina C no amena a las del resto del tablero y despues se comprueba el resto del tablero.

amenaza(X,Y). se verifica si una reina colocada en la columna X de la fila n de un tablero amenaza a cualquiera de las demás reinas colocadas en las filas 0..n-1 del resto del tablero, y cuyas columnas vienen especificadas en la lista Y. Utiliza para comprobar todo esto el predicado análogo amenaza(X,Prof,L), que se cumple cuando X y otro elemento de la lista L se encuentran en la misma columna (mismo valor) o especifican reinas situadas en diagonal.

amenaza(X,Prof,[C|_]):- X is C+Prof;
X is C-Prof;
X = C.
amenaza(X,Prof,[_|R]):- ProfMas1 is Prof + 1,
amenaza(X,ProfMas1,R).


amenaza(_,[]):- fail.
amenaza(X,Y):- amenaza(X,1,Y).

Análisis de la solución propuesta

Anuncios

Etiquetas: , , ,

22 comentarios to “Implementación del problema de las N-Reinas en Prolog (programación lógica)”

  1. david Says:

    el programa funciona pero al escribir la respuesta no la muestra completa, implemente un print para ver la lista final completa y si la muestra completa pero al asignar el resultado a la variable y mostrarla en pantalla no la muestra commpleta, por que pasa eso?,,,,,que me recomiendas hacer para corregirlo?,,,,,,,,,espero me contesten lo antes posible,,,gracias

  2. prodor Says:

    Ok. Gracias, pero creo que se cicla cuando tienes mas de 10 x 10 casillas… y 10 reinas… o es mi 486 con memoria de 2 mb… xD

  3. marbaez Says:

    prodor: si que funciona con más de 10 reinas, lo que ocurre es que la cantidad de operaciones que tiene que hacer y los resultados que muestra es brutal. Lo he ejecutado con mi core2 duo y 2gb de ram y tarda un ratito. Yo utilizao el SWI-Prolog como intéprete de Prolog, ¿Cual estás utilizando tú?

  4. marbaez Says:

    david: eso lo hace swi-prolog cuando la lista es muy larga. Para ver la lista completa puedes hacer un nuevo predicado del tipo:
    imprimirReinas(Num,Tablero):-nreinas(Num,Tablero),write(Tablero).
    y así te muestra todo el tablero.

    Espero que te sirva

  5. david Says:

    hola a todos ya resolvi el problema que tenia,,,,,solo tenia que configurar el archivo init que esta en el menu settings, use init file quito los comentarios de la parte que controla el tamaño de la salida y lo redimensiono y ya,,,por si alguien tiene el mismo problema asi se resuelve,,,bye

  6. david Says:

    gracias a todos por su ayuda 🙂

  7. marbaez Says:

    de nada david, me has hecho aprender algo a mi tambien

  8. karina Says:

    hola!! necesito ayuda con el problema de las 8 reinas para 1 solucion si pueden el pseudo formal mejor xfa. gracias. lo mas rapido posible.

  9. marbaez Says:

    hola karina!
    En el post tienes el problema completo en Prolog para cualquier tamaño de tablero, y solo te da más soluciones si tu se las pides.

  10. rafael Says:

    disculpa david, que interprete de prolog utilizas ? fue el swi-prolog o algun otro ?

  11. Pedro Says:

    No entiendo que debe ir en Sol
    Por ejemplo, para que me de una solucion en un tablero de 8×8 debo hacer esto o no?
    nreinas(8,[]).
    En ese caso me indica
    ERROR: toplevel: Undefined procedure: nreinas/2 (DWIM could not correct goal)

    Por favor, necesito ayuda urgente

  12. david Says:

    disculpa que te conteste hasta ahora,,, use swi-prolog para correr el programa y modifique el archivo init como lo describi unos comentarios arriba si tienes broncas mandame un mail mi correo es de hotmail james_gordo espero te sirva de algo rafa

  13. david Says:

    a ver pedro correlo de esta forma: nreinas(8,S).
    te debe de funcionar asi saludos

  14. Edgar Says:

    mira tengo estos inconvenientes cuando voy corriendo

    ?- buenTablero([C|R]).
    ERROR: is/2: Arguments are not sufficiently instantiated
    ^ Exception: (11) _G180 is _G267+1 ? No previous search
    ^ Exception: (11) _G180 is _G267+1 ? creep
    Exception: (10) amenaza(_G180, 1, _G181) ? creep
    ?- not(amenaza(C,R)).

    ERROR: is/2: Arguments are not sufficiently instantiated
    ^ Exception: (10) _G180 is _G266+1 ? creep
    Exception: (9) amenaza(_G180, 1, _G181) ? creep

    no entiendo porque se genera y que es _G180

    al final implemente el predicado para imprmr hago mi nreinas(8,S). y luego quiero escribirlo pero solo me muestra

    ?- write(S).
    _G180
    true.
    que es porfa ayuda

  15. marbaez Says:

    Pedro en Sol debe de ir una variable sin instanciar (Letra o palabra que comience por mayusculas) o un tablero en tu caso de dimensión 8 del tipo [X,X,X,X,X,X,X,X] donde las X son posiciones del 1 al 8.
    Si utilizas el tablero este tiene que tener un número de elementos que coincida con el número de posiciones que le has indicado en el predicado, es decir nReinas(8, [1,2,3,4,5,6,7,8]) funcionaria y te daria false como resultado porque no forman un tablero correcto, pero nReinas(8,[1,2]) o nReinas(8,[]) te darían error al ejecutarlo porque no corresponde el número de elementos que le estás indicando que tiene el tablero, con el número de elementos que estás poniendo en el tablero de entrada.

  16. charly Says:

    hola me puedes decir con que predicados corre el programa es q no se con cuales

  17. yeyi Says:

    ola, alguien tendra un programa de 4 reinas en prolog que pida las posiciones para colocar las reinas. me urge!!!
    grax

  18. Javier Angosto Says:

    Aquí tenéis la implementación en Java de las N-Reinas: http://fangosto.blogspot.com/2011/03/java-juego-n-reinas-avance.html

  19. L Says:

    ¿En donde verifica la amenza… ‘Prof’ es algo así como la ‘Prof’undidad de las filas o columnas?

  20. augenlasern Says:

    Everything is very open with a precise clarification of
    the challenges. It was truly informative. Your site is very
    helpful. Thank you for sharing!

  21. Mannheim Kindergeburtstag Says:

    I will immediately take hold of your rss as I can not in
    finding your e-mail subscription hyperlink or newsletter service.

    Do you’ve any? Please let me realize in order that I could subscribe. Thanks.

  22. jeanpieerbarracuentas Says:

    si por favor seria exelente que puedas poner los comandos con los cuales corre los resulatos de

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s


A %d blogueros les gusta esto: