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

Intelligence artificielle Discussion :

[IA] Creer un sudoku (algorithme pour le moment)


Sujet :

Intelligence artificielle

  1. #1
    Membre du Club
    Inscrit en
    avril 2007
    Messages
    122
    Détails du profil
    Informations forums :
    Inscription : avril 2007
    Messages : 122
    Points : 63
    Points
    63
    Par défaut [IA] Creer un sudoku (algorithme pour le moment)
    Bonjour tout le monde.

    J'ai donc un projet a faire et on a refléchit avec des amis mais on arrive vraiment a rien.

    Le but est de creer un sodoku (pas tres sympa pour des premieres année). Pour le moment on ne connait a peu pret rien en gtk( afficher les fenetre etc...) on s'est donc concentré sur l'algorithme.

    On a pensé faire cela:
    Creer un tableau a deux dimension 9*9. Mettre des chiffre compris entre 0 et 9 dans chaque cellule et vérifier ensuite si c'est bien un sudoku puis effacer certain nombre et voila.

    Mais le probleme c'est que en generant des nombre aleatoirement il faudrai peut etre qq heures au pc avant de trouver un sudoku. Donc on s'est dit que c'est mort pour cette technique.

    Donc j'aimerais collecter vos idées generer un sudoku.

    Merci infiniement

  2. #2
    Membre régulier
    Homme Profil pro
    Architecte logiciel
    Inscrit en
    novembre 2006
    Messages
    93
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte logiciel

    Informations forums :
    Inscription : novembre 2006
    Messages : 93
    Points : 90
    Points
    90
    Par défaut
    cherche sur le net des algos il doit bien yen avoir sur le net pour générer des sudokus


    perso moi je sais pas sorry mais c'est sur qu'avec tes aléatoires

  3. #3
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 51

    Informations forums :
    Inscription : octobre 2003
    Messages : 1 106
    Points : 1 199
    Points
    1 199
    Par défaut
    Nan, ne cherche pas sur le net, CHERCHE sut developpez, y a eu un topic avec 175532325 réponses....

    ... on cherche d'abord, on pose une question ensuite!!!
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  4. #4
    Membre du Club
    Inscrit en
    avril 2007
    Messages
    122
    Détails du profil
    Informations forums :
    Inscription : avril 2007
    Messages : 122
    Points : 63
    Points
    63
    Par défaut
    Je suis déolé. J'avais cherché mais pas sur le bon forum.

    Merci je vais lire tous les sujets et reviendrai apres.

  5. #5
    Membre régulier Avatar de thomas9501
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : décembre 2006
    Messages : 102
    Points : 114
    Points
    114
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    Nan, ne cherche pas sur le net, CHERCHE sut developpez, y a eu un topic avec 175532325 réponses....

    ... on cherche d'abord, on pose une question ensuite!!!
    Si tu pouvais nous donner le lien de ce topic ce serai sympa parce que j'ai cherché partout sur Developpez.net et je ne trouve aucun topic qui résout ce problème sur lequel je bute également
    On n'est pas le meilleur quand on le croit mais quand on le sait !!

  6. #6
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    [HS]
    A mon avis, avant de résoudre le sudoku, il faudra apprendre à savoir utiliser la fonction recherche
    [/HS]

    http://www.developpez.net/forums/showthread.php?t=54373

  7. #7
    Membre régulier Avatar de thomas9501
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : décembre 2006
    Messages : 102
    Points : 114
    Points
    114
    Par défaut
    Je ne cherche pas un solutionneur de grille de sudoku mais un algorithme de génération d'une grille de sudoku.
    On n'est pas le meilleur quand on le croit mais quand on le sait !!

  8. #8
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    En fait, générer une grille, c'est résoudre un sudoku issu d'une grille vide.

  9. #9
    Membre régulier Avatar de thomas9501
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : décembre 2006
    Messages : 102
    Points : 114
    Points
    114
    Par défaut
    Finalement, j'ai utilisé cette méthode pour générer une grille de sudoku aléatoirement :
    http://sudoku.nerdzblog.com/index.php?idb=104

    Voici le programme java que j'ai réalisé, un jeu de Sudoku :
    http://dl.toofiles.com/kp8k4c/documents/sudoku.zip
    On n'est pas le meilleur quand on le croit mais quand on le sait !!

  10. #10
    Membre averti

    Profil pro
    Étudiant
    Inscrit en
    décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 35
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : décembre 2004
    Messages : 499
    Points : 429
    Points
    429
    Par défaut
    berk les permutations !

    le backtracking avec la simple heuristique de choisir la case qui a le moins de possibles fonctionne bien

    sinon le plus efficace je pense est d'utiliser un SAT solver pour trouver les solutions d'une grille

    il suffit de traduire en booléen:
    au moins un chiffre par case, au max un chiffre par case, chaque chiffre apparait au moins une fois par colonne ligne bloc, au max une fois par colonne ligne bloc

    on a 9 variables booléennes par case ce qui fait 9*81 variables booléennes en tout

    attention: le SAT solver est par excellence l'outil qui ne permettra pas facilement de générer aléatoirement des grilles, pour ça il vaut mieux utiliser en plus le backtracking

    Renaud

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

Discussions similaires

  1. Créer un tache crom pour redemarrer un serveur Mandrake
    Par crumbles34 dans le forum Administration système
    Réponses: 6
    Dernier message: 29/11/2005, 11h10
  2. Quel algorithme pour insertion d'objets "triés" da
    Par phplive dans le forum Langage
    Réponses: 3
    Dernier message: 04/08/2005, 10h27
  3. Algorithme pour trier trois nombres
    Par legosam dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 17/01/2005, 22h47
  4. Creer une nouvelle référence pour le driver ODBC
    Par tripper.dim dans le forum Connexion aux bases de données
    Réponses: 3
    Dernier message: 04/01/2005, 23h57
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 11h47

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