Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 sudoku

Voir le sujet précédent Voir le sujet suivant Aller en bas 
Aller à la page : Précédent  1, 2, 3  Suivant
AuteurMessage
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Lun 26 Mar - 21:54

Oui ça a marché avec cette grille aussi :

Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Lun 26 Mar - 21:55

J'ai enlevé l'affichage des actions pour que ça soit plus claire :

Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 0:14

Voici une autre grille qui met assez de temps pour être résolue :
1 _ _|_ _ _|3 _ 9
_ _ _|_ 6 _|_ 2 _
3 _ 9|_ _ _|5 _ 7
------------------
5 _ 7|_ _ _|_ _ 4
_ _ _|_ 8 _|_ _ _
6 _ _|2 _ _|8 _ 5
------------------
2 _ 4|_ _ _|9 _ 6
_ _ _|_ _ _|_ 4 _
9 _ 6|_ _ 2|7 _ 8


J'ai utilisé une autre méthode pour trouver un résultat. Elle met trop de temps plus de 45 minutes.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 0:20

Je vois que c'est la même depuis le début, mais avec moin de chiffre au départ.
Mon programme l'a résolu en une seconde (ou même moin).
Alors vous voulez voir le code ou pas encore ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 0:26

Je voudrais que mtcs essaye aussi de résoudre ce problème. Alors ne postes pas le code maintenant jusqu'à ce qu'il essaye de trouver une solution.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 0:29

C'est vous qui voyez.
Je voudrais savoir comment tu as fait pour résoudre en retrouvant un seule résultat ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 0:31

mtcs a écrit:
felicitation Chaker Idea
Tu es invité à trouver une solution aussi avant que chaker ne poste sa réponse.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 15:27

chakerbh a écrit:
C'est vous qui voyez.
Je voudrais savoir comment tu as fait pour résoudre en retrouvant un seule résultat ?
Chakerbh je souhaiterai que tu testes cette grille :
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _
------------------
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _
------------------
_ _ _|_ _ _|9 _ _
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _

Normalement la grille ne doit pas être résolue par tatonnement. Ce que tu as fais dans ton programme c'est un générateur de grille sudoku.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 15:46

En utilisant des valeurs aléatoires. L'exécution met de 2 secondes à quelques minutes pour trouver un résultat pour la grille initiale suivante. Il faudrait que j'optimise ma méthode.

Grille Initiale
1 _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ _
_ _ 3|_ _ _|_ _ _
------------------
_ _ _|4 _ _|_ _ _
_ _ _|_ _ _|_ _ _
_ _ _|_ _ 6|_ _ _
------------------
_ _ _|_ _ _|7 _ _
_ _ _|_ _ _|_ _ _
_ _ _|_ _ _|_ _ 9

Grille Finale
1 6 7|8 2 5|9 4 3
5 4 9|3 6 1|2 8 7
2 8 3|7 9 4|6 5 1
------------------
7 2 8|4 3 9|1 6 5
9 1 6|2 5 8|3 7 4
4 3 5|1 7 6|8 9 2
------------------
8 5 4|9 1 3|7 2 6
3 9 2|6 4 7|5 1 8
6 7 1|5 8 2|4 3 9
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: sudoku   Mar 27 Mar - 16:10

j'ai trouvé une solution mais malheureusement ne marche pas avec tout le grille, mnt je vais esseyer avec les chaine de caractaire.

si vous vouez poster vos solution aller et je vous promis que je ne les voi pas
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 16:50

mtcs en suivant la méthode que j'avais énoncé précédemment et en suivant les explications de chakerbh tu pourra y arriver certainement.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 17:03

Mon programme a résolu les deux grille en moin de 3 secondes.
Mais j'aimerais comprendre quelque chose : est ce que résoudre une grille c'est bien retourner une grille compléte avec les valeurs de départ données ?
Et puis lorsqu'on donne au programme une grille dont on peut avoir plusieur résultat, comment obtenir un seule résultat ?
La premiére grille de test n'admet qu'un seule résultat, alors on n'a pas eu besoin de choisir des valeur au hazard et tous nos programme retournaient le même résultat.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: sudoku   Mar 27 Mar - 17:05

j'ai suivé votre méthode (meme j'ai le modifier un peut) et j'ai arrivé à resolu des grille dans une seconde, et d'autre mon PC planter (PII, memoire vive 128Mo, y at il une relation entre ces caracteristique et le programme de sudoku?) merci encore
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 17:29

mtcs
Si la méthode que tu as utilisé essaye toutes les combinaisons possibles comme je l'avais fait ton programme mettra beaucoup de temps et c'est la raison de la lenteur de mon programme. Pour la méthode que j'utilise elle dépend de la fréquence du microprocesseur et de la configuration matérielle.
La méthode de chakerbh est plus efficace.

chakerbh
Une grille sudoku est tout d'abord résolue par la logique d'ou le résultat était identique qu'on obtenait pour la première grille. Ensuite si la logique ne donne pas ces fruits on procède par tatonnement d'ou la possiblité d'obtenir plus qu'une solution. Alors, il ne faut pas rêver dans ce dernier cas de solution unique.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 17:33

Very Happy:D:D:D:D

J'ai prévu le cas où la logique apporte ses fruits. Le tatonnement n'entre en jeu que lorsqu'on ne trouve aucune valeur à inserrer par la logique.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 17:42

J'ai trouvé pourquoi mon programme met autant de temps pour trouver des résultats c'est ma présumée optimisation qui ralentissait mon programme.
Mon optimisation consistait à récupérer la liste des points encore vide aprés la résolution par la logique puis de les trier par ordre d'importance celui qui admet plus de solutions au début ensuite d'effectuer quelques tirages au sorts sur ces points. L'opération incorrecte était le tri en l'enlevant le programme fonctionne plus rapidement même avec une grille vide.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 19:14

Alors on partage nos codes ou pas encore ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
manianis
V.I.P
V.I.P
avatar

Nombre de messages : 471
Age : 107
Date d'inscription : 19/03/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:18

Oui bien sur... Je posterai mon code peut être demain car je ne suis pas chez moi pour l'instant.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://manianis.sitesled.com/
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:21

Alors je vais commencer par mon code, avec une petite explication bien sur
||
||
||
\/
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:36

J'ai modifé la procédure finale comme suit :
Code:
procedure finale(var T:TTab);
  var nb,c:integer;
      T1:ttab;
      Ta:boolean;
  begin
    Ta:=false;
    c:=0;
    repeat
      inc(c);
      nb:=calcul(T);
      verifL(T);
      verifC(T);
      verifCa(T);

      if (calcul(T)=nb) then
          begin
          if not Ta then copie(T,T1);
          if test(T) then copie(T1,T);
          Ta:=true;
          tatone(T);
          end;
    until (nb>=81)OR(c=1000);
  end;


Le compteur c sert à éviter les boucles infinies.
Les procédures verifL, verifC et verifCa peremttent d'inserrer les valeurs dont on est sure (par la logique) à leurs places et ces procédures vérifient (comme leur noms l'indiquent) chaque ligne, chaque colonne et chaque carreau.
La procédure tatone inserre une valeur au hazard, mais avant le premier appel à cette procédure (je le détecte à l'aide du flag Ta) je sauvegarde la version de la grille obtenue par la logique dans le tableau T1 (qui est de même type que T) à l'aide de la procédure copie qui copie un premier tableau dans un deuxiéme.
En fin, la fonction test retourne vrai si il ya une case vide mais on en peut y inserrer aucune valeur (exemple : un carreau contien tous les chiffres à par 9, mais on a déja inserrer un 9 dans cette ligne), sinon elle retourne faux.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:42

Puis voici les codes des fonctions et procédures que j'ai utilisé dans la procédure finale :

  • calcul :
    Code:
    function calcul(T:TTab):integer;

      var i,j,nb:integer;

      begin

        nb:=0;

        for i:=1 to 9 do

          for j:=1 to 9 do

            if T[i,j]<>0 then inc(nb);

        calcul:=nb;

      end;
  • copie :
    Code:
    procedure copie(T1:TTab;var T2:TTab);
      var i,j:integer;
      begin
        for i:=1 to 9 do
          for j:=1 to 9 do
            T2[i,j]:=T1[i,j];
      end;
  • test :
    Code:
    function nb_pos(T:TTab;i,j:integer):integer;
      var n,k:integer;
      begin
        k:=0;
        for n:=1 to 9 do
          if not (existeL(T,i,j,n) OR existeC(T,i,j,n) OR existeCa(T,i,j,n)) then inc(k);
        nb_pos:=k;
      end;

    function test(T:TTab):boolean;
      var i,j:integer;
          ok:boolean;
      begin
        ok:=false;
        for i:=1 to 9 do
          for j:=1 to 9 do
            if (nb_pos(T,i,j)=0)AND(T[i,j]=0) then ok:=true;
        test:=ok;
      end;
  • verifL :
    Code:
    procedure verifL(var T:TTab);
      var i,j,n,k:integer;
          T1:Tij;
      begin
        for i:=1 to 9 do       
          for n:=1 to 9 do
            begin
              k:=0;
              for j:=1 to 9 do
                if (T[i,j]=0)AND not (existeC(T,i,j,n) OR existeL(T,i,j,n)
                    OR existeCa(T,i,j,n)) then
                  begin
                      k:=k+1;
                      T1[k].i:=i;
                      T1[k].j:=j;
                  end;
              if k=1 then T[T1[k].i,T1[k].j]:=n;
            end;
      end;
  • verifC :
    Code:
    procedure verifC(var T:TTab);
      var i,j,k,n:integer;
          T1:Tij;
      begin
        for j:=1 to 9 do
          for n:=1 to 9 do
            begin
              k:=0;
              for i:=1 to 9 do
                if (T[i,j]=0)AND not (existeC(T,i,j,n) OR existeL(T,i,j,n)
                  OR existeCa(T,i,j,n)) then
                  begin
                    k:=k+1;
                    T1[k].i:=i;
                    T1[k].j:=j;
                  end;
              if k=1 then T[T1[k].i,T1[k].j]:=n;
            end;
      end;
  • verifCa :
    Code:
    procedure verifCa(var T:TTab);
      var i,j,k,n,i1,j1:integer;
          T1:Tij;
      begin
        for i1:=0 to 2 do
          for j1:=0 to 2 do
              for n:=1 to 9 do
                begin
                  k:=0;
                  for i:=i1*3+1 to i1*3+3 do
                    for j:=j1*3+1 to j1*3+3 do
                      if (T[i,j]=0)AND not (existeC(T,i,j,n) OR existeL(T,i,j,n)
                            OR existeCa(T,i,j,n)) then
                        begin
                          k:=k+1;
                          T1[k].i:=i;
                          T1[k].j:=j;
                        end;
                  if k=1 then T[T1[k].i,T1[k].j]:=n;
                end;
      end;
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:45

J'ai oublié les codes des fonctions existeC, existeCa et exsiteL
Code:
function existeCa(T:TTab;i,j,N:integer):boolean;
  var l,c:integer;
      ok:boolean;
  begin
    ok:=false;
    if i<=3 then i:=0
    else if i<=6 then i:=1
    else i:=2;
    if j<=3 then j:=0
    else if j<=6 then j:=1
    else j:=2;

    for l:=i*3+1 to i*3+3 do
      for c:=j*3+1 to j*3+3 do
        if T[l,c]=N then ok:=true;
    existeCa:=ok;
  end;
 
function existeL(T:TTab;i,j,N:integer):boolean;
  var c:integer;
      ok:boolean;
  begin
    ok:=false;
    for c:=1 to 9 do
      if T[i,C]=N then ok:=true;
    existeL:=ok;
  end;

function existeC(T:TTab;i,j,N:integer):boolean;
  var l:integer;
      ok:boolean;
  begin
    ok:=false;
    for l:=1 to 9 do
      if T[l,j]=N then ok:=true;
    existeC:=ok;
  end;
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 20:47

Alors Manianis fais des tests et donne moi ton avi.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: sudoku   Mar 27 Mar - 23:02

Toi aussi Mohamed je t'invite à tester mon code et à me donner ton avi, et tous les autres membres biensûre Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: sudoku   Mar 27 Mar - 23:09

ok mon ami, mais apres que je reusi à resordre le jeu, puisque j'ai promi de ne pas le voir, dsl. mais je compte sur toi
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: sudoku   

Revenir en haut Aller en bas
 
sudoku
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 2 sur 3Aller à la page : Précédent  1, 2, 3  Suivant
 Sujets similaires
-
» [PROJET] sudoku
» SUDOKU solution

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Exercices-
Sauter vers: