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

Lisp Discussion :

Implémentation du jeu Sudoku en Common Lisp


Sujet :

Lisp

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Septembre 2012
    Messages : 16
    Points : 16
    Points
    16
    Par défaut Implémentation du jeu Sudoku en Common Lisp
    Bonsoir,
    Je dois implémenter le jeu sudoku en Lisp et je voulais savoir quel choix d'implémentation est le plus simple entre un tableau à deux dimensions et un objet d'objets.
    En effet j'ai commencé par ne créer qu'un tableau à deux dimenssion je me suis rendu compte que j'ai des problèmes pour gérer les carrés de la grille sudoku. En objet je ne sais pas du tou comment generer la grille.
    En vous remerciant d'avance pour vos réponses.

  2. #2
    Membre actif
    Homme Profil pro
    Inscrit en
    Mai 2013
    Messages
    152
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mai 2013
    Messages : 152
    Points : 275
    Points
    275
    Par défaut
    Citation Envoyé par atosbi Voir le message
    En effet j'ai commencé par ne créer qu'un tableau à deux dimenssion je me suis rendu compte que j'ai des problèmes pour gérer les carrés de la grille sudoku.
    Quelle sorte de problèmes ?

  3. #3
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Bonjour.
    Tu le fais en Common Lisp ou en CLOS?
    Si j'avais le choix, je le ferais en CLOS.
    Amha, tu as certainement moins besoin de puissance de calcul que de puissance de modélisation.
    As-tu commencé ton modèle?
    Quelles sont les méthodes dont tu as besoin?

  4. #4
    Membre actif
    Homme Profil pro
    Inscrit en
    Mai 2013
    Messages
    152
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mai 2013
    Messages : 152
    Points : 275
    Points
    275
    Par défaut
    Citation Envoyé par jack-ft Voir le message
    Tu le fais en Common Lisp ou en CLOS?
    Comment ça, CLOS fait partie de Common Lisp.

    Personnellement, je ne vois pas encore comment les fonctions génériques puissent être utiles dans ce cas.

  5. #5
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Citation Envoyé par byjav Voir le message
    Comment ça, CLOS fait partie de Common Lisp.
    Oui, bien sûr.

    Comme l'utilisateur parlait de "choix d'implémentation" et de "tableau à 2 dimensions", je voulais attirer son attention sur le choix d'un modèle abstrait, si possible indépendant de son implémentation.

    Se concentrer sur ce dont il a besoin avant de choisir comment l'implémenter.

    Personnellement, je ne vois pas encore comment les fonctions génériques puissent être utiles dans ce cas.
    Pour CLOS, je pensais plus à l'encapsulation qu'aux fonctions génériques.

    Bref, un bon modèle objet, koa!

    Après, il faudrait savoir quel genre d'interface utilisateur il veut.

    Et aussi et surtout, il faudrait savoir de quel genre de programme il s'agit:
    - un jeu interactif, partant d'une grille de départ donnée,
    - ou un programme pour résoudre une grille donnée
    - ou un programme pour générer des grilles.

  6. #6
    Membre actif
    Homme Profil pro
    Inscrit en
    Mai 2013
    Messages
    152
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mai 2013
    Messages : 152
    Points : 275
    Points
    275
    Par défaut
    Je suis d'accord. L'interface aux données est peut-être plus importante que l'implémentation des données.

  7. #7
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Septembre 2012
    Messages : 16
    Points : 16
    Points
    16
    Par défaut
    Désolé de ne pas avoir répondu. Comme je ne suis pas un habitué de ce forum je n'ai pas fait attention au message qui me disait que la discussion que j'avais créé avait été déplacée.
    Pour répondre à vos questions, je dois développer le jeux en Common Lisp, et j'hésitait à considérer ma grille comme un tableau à deux dimensions ou comme un ensemble d'objets (c'est-à-dire que chaque case est un objet).
    J'ai finalement choisi d'implémenter ma grille avec un tableau à deux dimensions.
    Cependant je dois maintenant créer une stratégie qui remplie une, grille de sudoku en moins de 20 ms.
    J'ai essayer de parcourir la grille dans un premier temps pour classer les cases où on peut jouer suivant le nombre de coups possibles de ces derniers dans une table de hashage.
    Ensuite j'ai une fonction qui parcours la table et pour chaque case, il essaie un chiffre parmi ceux possibles et ainsi de suite. Si dans une case aucun des chiffres possibles n'est valide alors on revient en arriere.
    Cette stratégie ne fonctionne pas car elle revient trop en arrière.

    Si quelqu'un voit comment je peux l'améliorer ou voit une autre stratégie plus efficace je suis preneur.

    Merci d'avance pour vos réponses.

  8. #8
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Citation Envoyé par atosbi Voir le message
    Pour répondre à vos questions, je dois développer le jeux en Common Lisp, et j'hésitait à considérer ma grille comme un tableau à deux dimensions ou comme un ensemble d'objets (c'est-à-dire que chaque case est un objet).
    J'ai finalement choisi d'implémenter ma grille avec un tableau à deux dimensions.
    ok

    Cependant je dois maintenant créer une stratégie qui remplie une, grille de sudoku en moins de 20 ms.
    Bon. Apparemment, c'est la réponse n°2:
    - un programme pour résoudre une grille donnée

    J'ai essayer de parcourir la grille dans un premier temps pour classer les cases où on peut jouer suivant le nombre de coups possibles de ces derniers dans une table de hashage.
    Bonne idée de classer les cases en fonction du nombre de coups possibles pour chacune.
    Dans les problèmes à base de contraintes, il est très souvent bon de commencer par les coups les plus contraints!
    Mais pourquoi une table de hashage?

    Ensuite j'ai une fonction qui parcours la table et pour chaque case, il essaie un chiffre parmi ceux possibles et ainsi de suite. Si dans une case aucun des chiffres possibles n'est valide alors on revient en arriere.
    Cette stratégie ne fonctionne pas car elle revient trop en arrière.

    Si quelqu'un voit comment je peux l'améliorer ou voit une autre stratégie plus efficace je suis preneur.
    Ben, ç'a l'air pas trop mal.
    Il faut juste gérer proprement le backtrack.

    A priori, et sans trop réfléchir (et dans une première version non optimisée), je parcourrais la liste des cases non affectées et créerais une a-list avec la case (peut-être un couple (i, j)) et la liste des nombres possibles pour la case.
    Ensuite, un coup de "sort" pour trier la a-list en mettant en tête les cases dont la liste de possibilités sont les plus courtes.
    Ensuite, on parcourt la liste:
    Si la liste associée au premier élément est vide, c'est que le dernier essai est pas bon => backtrack
    Si la liste associée au premier élément contient un seul nombre, c'est un coup forcé, on le fait et on continue.
    Si la liste associée au premier élément contient plusieurs nombres, il faut les essayer, mais en se donnant la possibilité de revenir en arrière.

    Pour pouvoir revenir en arrière, il faut soit compter sur la pile de récursivité, soit le gérer à la main.

    La méthode brute consiste à dupliquer tout le tableau pour chaque essai.
    Du coup, quand on revient en arrière dans la récursivité, on retrouve les données telles qu'elles étaient avant l'essai.

    Écris-nous ton algorithme et on te dira ce qu'on en pense.

  9. #9
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Septembre 2012
    Messages : 16
    Points : 16
    Points
    16
    Par défaut Mais pourquoi une table de hashage?
    J'ai choisi la table de hachage parce qu'un accès à elle coûte moins chère.

  10. #10
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Septembre 2012
    Messages : 16
    Points : 16
    Points
    16
    Par défaut Écris-nous ton algorithme et on te dira ce qu'on en pense.
    les clés pour les accès a la table vont de 1 au nombre de case vide (dans la grille). Et chaque case contient un objet Box qui contient les coordonnées de la case, la valeur jouée et la liste des possibilités sur cette case (dans la quelle on ajoute 0 en queue de liste).

    Algo:

    --->strategy (grille, table, index)
    ----> dernier-index = taille(table)
    ----> si getValeur(table, dernier-index) != 0 alors
    ---->retrourner true;
    ----> sinon
    ---->si jouerUnCoup(grille, table, index) == true alors
    ----> strategy (grille, table, (index+1));
    ---->sinon
    ----> strategy(grille, table, (index-1))


    Pour la fonction jouerUnCoup
    ---->jouerUnCoup (grille, table, index)
    ---->play = false
    ---->si premierElementListe(table, index) == 0 alors
    ---->on la place en queue de liste
    ----> retourner false;
    ---->sinon
    ---->Tant premierElementListe(table, index)!= 0 et play == false faire
    ---->si valide(grille, premierElementListe(table, index), getX(table, index), getY(table, index)) alors
    ---->grille[getX(table, index)][getY(table, index)] = premierElementListe(table, index)
    ---->setValeur(table, index, premierElementListe(table, index))
    ---->play = true
    ----> on la place le premier element en queue de liste
    ---->retuourner play




    Sauf que dans ce cas il fait une boucle infinie ou essaie d'accéder la l'index 0 de la table de hachage (ce qui n'existe pas).

  11. #11
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Citation Envoyé par atosbi Voir le message
    J'ai choisi la table de hachage parce qu'un accès à elle coûte moins chère.
    Je sais bien qu'une hashtable permet un accès plus rapide, mais c'est pas clair ce que tu utilises comme structure...

    Citation Envoyé par atosbi Voir le message
    les clés pour les accès a la table vont de 1 au nombre de case vide (dans la grille). Et chaque case contient un objet Box qui contient les coordonnées de la case, la valeur jouée et la liste des possibilités sur cette case (dans la quelle on ajoute 0 en queue de liste).
    Pour formatter du texte (surtout avec des espaces), il faut utiliser la balise CODE, par exemple en cliquant sur le dièse # de la barre. (je ne peux pas modifier ton message)

    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
    22
    23
    24
    25
    26
    27
    Algo:
     
    --->strategy (grille, table, index)
        ----> dernier-index = taille(table)
        ---->  si getValeur(table, dernier-index) != 0 alors
               ---->retrourner true;
        ----> sinon 
              ---->si jouerUnCoup(grille, table, index) == true alors
                    ----> strategy (grille, table, (index+1));
              ---->sinon
                    ----> strategy(grille, table, (index-1))
     
     
    Pour la fonction jouerUnCoup
    ---->jouerUnCoup (grille, table, index)
          ---->play = false
          ---->si premierElementListe(table, index) == 0 alors
                ---->on la place en queue de liste 
                ----> retourner false;
          ---->sinon
                ---->Tant premierElementListe(table, index)!= 0 et play == false faire
                      ---->si valide(grille, premierElementListe(table, index), getX(table, index), getY(table, index)) alors
                            ---->grille[getX(table, index)][getY(table, index)] = premierElementListe(table, index)
                            ---->setValeur(table, index, premierElementListe(table, index))
                            ---->play = true
                      ----> on la place le premier element en queue de liste 
          ---->retuourner play
    Ma proposition d'algorithme serait la suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Pour résoudre (grille)
      si grille est résolue
      alors retourner la grille
      pour chaque case de la grille
        si la case est non affectée
        alors stocker pour cette case la liste des valeurs possibles
      trouver la case la plus contrainte, ayant le moins de valeurs possibles (on aurait intérêt à le faire pendant l'énumération précédente)
      si cette case n'a aucune possibilité
      alors retourner nil
      pour chaque possibilité de cette case
        résoudre la grille obtenue en jouant cette possibilité
        et cumuler et retourner les résultats obtenus
    Je te code ça ce soir et te donne le résultat demain...

  12. #12
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Septembre 2012
    Messages : 16
    Points : 16
    Points
    16
    Par défaut Je te code ça ce soir et te donne le résultat demain...
    Merci. C'est vraiment gentillle.

  13. #13
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Citation Envoyé par jack-ft Voir le message
    Pour formatter du texte (surtout avec des espaces), il faut utiliser la balise CODE
    Ou bien indenter avec des tirets...

    Je te code ça ce soir et te donne le résultat demain...
    Une semaine plus tard... l'algo a quelque peu évolué...

    Pour résoudre (grille-brute)
    ---- pour chaque solution de trouver-solutions (construire-grille grille-brute)
    -------- imprimer solution
    ---- fin pour
    fin pour

    Pour trouver-solutions (grille)
    ---- // D'abord on joue tous les coups forcés
    ---- tant qu'il reste une case avec une seule valeur possible
    -------- suivant résultat après avoir mis cette valeur dans cette case:
    ----------- * solution: arrêter trouver-solutions et retourner cette solution
    ----------- * échec: arrêter trouver-solutions et retourner rien
    ----------- * ok: continuer
    -------- fin suivant
    ---- fin tant que

    ---- // Plus de coups forcés: il faut commencer le backtrack

    ---- choisir la case la plus contrainte
    ---- collecter
    -------- pour chaque valeur possible pour cette case
    ------------ copier la grille en une nouvelle grille
    ------------ suivant résultat après avoir mis cette valeur dans cette case de la nouvelle grille:
    --------------- * solution: collecter cette solution
    --------------- * échec: collecter rien // y a peu de chances...
    --------------- * ok: collecter trouver-solutions de cette nouvelle grille
    ------------ fin suivant
    -------- fin pour
    ---- fin collecter
    ---- retourner le résultat de la collecte
    fin pour

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [Débutant] Programmer le jeu Sudoku en Java
    Par whally dans le forum Graphisme
    Réponses: 5
    Dernier message: 04/03/2011, 10h53
  2. Comment installer Common Lisp sur Mac os X?
    Par ramm04 dans le forum Apple
    Réponses: 2
    Dernier message: 16/12/2009, 08h13
  3. ACL2 et Common Lisp?
    Par maissa019 dans le forum Lisp
    Réponses: 4
    Dernier message: 19/04/2008, 17h03
  4. Implémentation du jeu Sudoku
    Par DDartz dans le forum MATLAB
    Réponses: 1
    Dernier message: 28/05/2007, 19h04

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