IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Prolog Discussion :

Génération d'états d'une grille


Sujet :

Prolog

  1. #1
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut Génération d'états d'une grille
    Bonjour,
    J'ai une grille 3x3, chaque case à deux états possible, soit pleine soit vide !
    On représente l'état de la grille par une liste de listes :
    Exemple :
    [ [p,v,v], % la case 1 de la ligne 1 est pleine
    [v,v,v], %toute la ligne 2 est vide
    [v,v,v] ] %toute la ligne 3 est vide

    Je cherche à écrire un prédicat qui génère tous les états possibles à partir d'un état donné, sachant que d'un état à l'autre, on a droit à toucher une ligne ou une colonne (pas la diagonale) et de modifier une à plusieurs cases voir tous les cases d'une ligne ou d'une colonne.
    Exemple de génération d'états d'une grille 2x2 vide ([[v,v][v,v]]) :
    [[v,v],[v,p]]
    [[v,v],[p,v]]
    [[v,v],[p,p]]
    [[p,v],[v,v]]
    [[v,p],[v,v]]
    [[p,p],[v,v]]
    [[p,v],[p,v]]
    [[v,p],[v,p]]

    On a pas le droit de générer par exemple l'état : [[p,v],[v,p]]

    Merci pour votre aide .

  2. #2
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Tout d'abord, tu écris le prédicat qui, à partir d'une ligne, génère tous les changements possibles sur la ligne.

    En utilisant le prédicat précédent, tu écris le prédicat qui, à partir d'une grille, génère tous les changements portant sur des lignes.

    Ensuite, tu écris le prédicat qui effectue la transposée de la grille (les colonnes deviennent des lignes et les lignes des colonnes) et tu procèdes ainsi:
    - transposer la grille
    - générer les changements possibles sur des lignes
    - transposer la grille
    De cette manière, tu obtiens les grilles pour lesquelles des changements sont effectuées sur les colonnes.

    Voilà pour l'idée générale. Maintenant, dans le cas d'un changement sur une seule case, la solution est considérée à la fois comme un changement sur une ligne et comme un changement sur une colonne. Il faut que tu tiennes compte de cela pour ne pas générer de doublon.

    Maintenant, ça ne devrait plus te poser de problème.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  3. #3
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    voici le predicat qui fait les permutations d'une ligne donnée :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    permut([X],[X]).
    permut(L,[A|D]):-
        select(A,L,R),
        permut(R,D).
    Par contre on élimine pas les doublants !! comment faire alors ?

  4. #4
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    voici le predicat qui fait les permutations d'une ligne donnée :
    permut([X],[X]).
    permut(L,[A|D]):-
    select(A,L,R),
    permut(R,D).
    Oui mais... c'est qoi le rapport avec ton prolème de départ ?

    Et puis

    Citation Envoyé par cLaSic
    Par contre on élimine pas les doublants !! comment faire alors ?
    On n'en est pas encore là.

    Pour l'heure, implémente le prédicat:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    %%
    % changeLigne(+L, -NL, -C)
    %  +L : Ligne de départ
    %  -NL: Nouvelle ligne
    %  -C : Nombre de changements
    %
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  5. #5
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    Tout d'abord merci pour la réponse.
    Tout d'abord, tu écris le prédicat qui, à partir d'une ligne, génère tous les changements possibles sur la ligne.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    permut([X],[X]).
    permut(L,[A|D]):-
    select(A,L,R),
    permut(R,D).
    C'est pour cela que j'ai écris ce prédicat !
    permut marche bien, elle donne bien toutes les permutation possibles, mais dans mon cas je travail avec des listes qui contiennent des doublants ([p,p,v,v,p,p] ...) alors comment améliorer ce prédicat pour qu'il génère chaque permutation une et une seule foix.
    Le prédicat actuel me donne comme résultat :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    permut([p,p,v],X).
     
    X = [p, p, v] ;
    X = [p, v, p] ;
    X = [p, p, v] ;
    X = [p, v, p] ;
    X = [v, p, p] ;
    X = [v, p, p] ;
    Et moi je veux qu'il me retourne ca :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    permut([p,p,v],X).
     
    X = [p, p, v] ;
    X = [p, v, p] ;
    X = [v, p, p] ;
    Alors comment faire ?

  6. #6
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    permut n'a rien à voir avec le problème de départ :

    Citation Envoyé par cLaSic
    Je cherche à écrire un prédicat qui génère tous les états possibles à partir d'un état donné, sachant que d'un état à l'autre, on a droit à toucher une ligne ou une colonne (pas la diagonale) et de modifier une à plusieurs cases voir tous les cases d'une ligne ou d'une colonne.
    S'il s'agit d'un autre problème, ouvre un autre sujet.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  7. #7
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    Oui mais vous m'avez demandé tout d'abord d'écrire le prédicat qui, à partir d'une ligne, génère tous les changements possibles sur la ligne.
    C'est bien ca non ?

  8. #8
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    Oui mais vous m'avez demandé tout d'abord d'écrire le prédicat qui, à partir d'une ligne, génère tous les changements possibles sur la ligne.
    C'est bien ca non ?
    Ben non. Ce qu'il faut écrire, c'est un prédicat qui fait cela:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    | ?- changeLigne([v,v],R,C).
     
    R = [v, p],
    C = 1 ;
     
    R = [p, v],
    C = 1 ;
     
    R = [p, p],
    C = 2 ;
     
    No
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  9. #9
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    Citation Envoyé par pcaboche
    Ben non. Ce qu'il faut écrire, c'est un prédicat qui fait cela:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    | ?- changeLigne([v,v],R,C).
     
    R = [v, p],
    C = 1 ;
     
    R = [p, v],
    C = 1 ;
     
    R = [p, p],
    C = 2 ;
     
    No
    Je ne vois pas l'utilité du paramètre C !

    J'ai fais ca :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
    %predicat pour enlever un element de la liste
    remove_at(Elem,[Elem|Reste],1,Reste).
    remove_at(Elem,[Y|Reste],Position,[Y|Ys]) :- Position > 1,
       K1 is Position - 1, remove_at(Elem,Reste,K1,Ys).
     
    %predicat pour inserer un element dans la liste
    insert_at(Elem,Liste,Position,Resultat) :- remove_at(Elem,Resultat,Position,Liste).
     
    %predicat pour modifier un element de la liste
    modifierElement(Elem,Liste,Position,Resultat):-
        nth1(Position,Liste,v),%je ne modifie l'element que s'il est 'v'
        remove_at(_,Liste,Position,Reste),
        insert_at(Elem,Reste,Position,Resultat).
     
    %et changeLigne
    changeLigne([p,p],[p,p]).
    changeLigne(Liste,Resultat):-
        nth1(Position,Liste,v),
        modifierElement(p,Liste,Position,Resultat),
        changeLigne(Resultat,_).
    Mais j'ai pas le bon résultat :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     
    changeLigne([v,v,v],R).
     
    R = [p, v, v] ;
     
    R = [p, v, v] ;
     
    R = [v, p, v] ;
     
    R = [v, p, v] ;
     
    R = [v, v, p] ;
     
    R = [v, v, p] ;
     
    No

  10. #10
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    J'ai trouvé ca sur le net :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    changeLigne([],[]).
    changeLigne([v|Q1],[p|Q2]):-
      changeLigne(Q1,Q2).
    changeLigne([A|Q1],[A|Q2]):-
      changeLigne(Q1,Q2).
    Par contre il y'a parmi les résultats la liste entrée en paramètre.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    175 ?- changeLigne([v,v],X).
    
    X = [p, p] ;
    
    X = [p, v] ;
    
    X = [v, p] ;
    
    X = [v, v] ;
    
    No
    Comment faire pour résoudre cela ?
    Merci

  11. #11
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    Je ne vois pas l'utilité du paramètre C !
    C'est pour plus tard (pour la suppression des doublons).

    Citation Envoyé par cLaSic
    J'ai fais ca :
    Beaucoup trop compliqué, surtout pour un truc qui ne renvoie pas la bonne solution.

    Citation Envoyé par cLaSic
    Comment faire pour résoudre cela ?
    Simple: il suffit de réfléchir.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  12. #12
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    j'ai rajouté cette ligne au prédicat précèdent mais ça ne résout pas le problème !!
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    changeLigne(L,L):-!.

  13. #13
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    j'ai rajouté cette ligne au prédicat précèdent mais ça ne résout pas le problème !!
    C'est aussi à ça que sert C: pour que la solution soit correcte, il faut que C soit positif.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  14. #14
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    J'ai modifié le dernier prédicat :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    changeLigne2([],[],0).
    changeLigne2([v|Q1],[p|Q2],C):-
      C = D+1,
      C>0,
      changeLigne2(Q1,Q2,D).
    changeLigne2([A|Q1],[A|Q2],C):-
      changeLigne2(Q1,Q2,C).
    Normalement ça doit marcher !! j'ai essayé aussi C is D+1 !!

  15. #15
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    Normalement ça doit marcher !!
    Pas tout à fait.

    C'est seulement à la fin que tu dois tester si C>0.

    Tu oublies le cas où ta liste contient un p qu'il faut inverser en v. Utilise le prédicat suivant pour tes inversions:
    Citation Envoyé par cLaSic
    j'ai essayé aussi C is D+1 !!
    Il faut utiliser l'opérateur is pour les opérations arithmétiques, sinon ça a une autre signification.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  16. #16
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    Quand je fais que ça :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    changeLigne2([],[],0).
    changeLigne2([v|Q1],[p|Q2],C):-
      C = D+1,
      changeLigne2(Q1,Q2,D).
    changeLigne2([A|Q1],[A|Q2],C):-
      changeLigne2(Q1,Q2,C).
    ça ne me donne déjà pas le bon résultat
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     
    368 ?- changeLigne2([v,v],X,C).
     
    X = [p, p],
    C = 0+1+1 ; % je dois avoir C = 2
     
    X = [p, v],
    C = 0+1 ; % je dois avoir C = 1
     
    X = [v, p],
    C = 0+1 ; % je dois avoir C = 1
     
    X = [v, v],
    C = 0 ;
     
    No
    C'est pour cela que j'ai testé aussi l'opérateur 'is' mais ça n'a pas marché.

    Tu oublies le cas où ta liste contient un p qu'il faut inverser en v.
    Dans le jeu que je développe j'aurai pas ce cas :
    p:case pleine
    v:case vide
    Je dois remplir que les cases vides d'où le changement du 'v' en 'p'.

  17. #17
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par cLaSic
    ça ne me donne déjà pas le bon résultat
    Ben oui, 1+2, c'est le tuple +/2 composé des opérandes 1 et 2, c'est pas 3.

    Citation Envoyé par cLaSic
    C'est pour cela que j'ai testé aussi l'opérateur 'is' mais ça n'a pas marché.
    C'est sûr, si tu fais:
    mais que D n'est pas unifié, ça ne risque pas de marcher.

    Citation Envoyé par cLaSic
    Je dois remplir que les cases vides d'où le changement du 'v' en 'p'.
    C'est gentil de le préciser seulement maintenant. Quand tu parles de "changement d'état", ça donne l'impression que les états sont réversibles.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  18. #18
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    Avec D is C+1 ça ne marche pas non plus !
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    changeLigne2([],[],0).
    changeLigne2([v|Q1],[p|Q2],C):-
      D is C+1,
      changeLigne2(Q1,Q2,D).
    changeLigne2([A|Q1],[A|Q2],C):-
      changeLigne2(Q1,Q2,C).
    Je suis perdu là :\

  19. #19
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    J'y suis presque
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    changeLigne([],[],0).
    changeLigne([v|Q1],[p|Q2],C):-
      changeLigne(Q1,Q2,D),
      C is D+1,
      C>0.
    changeLigne([A|Q1],[A|Q2],C):-
      changeLigne(Q1,Q2,C).

  20. #20
    Membre à l'essai
    Inscrit en
    Août 2006
    Messages
    56
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 56
    Points : 22
    Points
    22
    Par défaut
    c'est fait.
    J'ai ajouté un prédicat qui fait appel à changeLigne et qui fait le test pour C>0.

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Génération d'une grille puzzle pour un jeu vidéo avec gestion de difficulté
    Par CaNiBaLe dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 04/07/2014, 17h49
  2. Réponses: 7
    Dernier message: 12/06/2012, 15h43
  3. Génération d'une grille de sudoku
    Par Amiraamir dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 31/12/2008, 12h53
  4. génération d'une grille de sudoku
    Par gnouz dans le forum Algorithmes et structures de données
    Réponses: 16
    Dernier message: 25/09/2008, 16h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo