Demande d'aide pour élaborer un algo pour un pb simple mais long

Version imprimable

Voir 40 message(s) de cette discussion en une page

20/11/2007, 01h28
fremen167

Citation:

Envoyé par Zavonen

Tu l'as fait exploser avec ton programme ?

:mouarf: Non, je crois pas, mais j'avais plus de disque dur :cry:

Citation:

Envoyé par Zavonen

Il faut compter le nombre de permutations laissant un par un globalement invariants les groupes de lignes djacentes égales et après diviser 9! par le produit des nombres trouvés.
Pour le moment, pas assez motivé pour continuer...

Pourtant c'est très simple : si une ligne se répète p fois, tu divises par p! (et cela pour chaque groupe de lignes égales).

Sinon, j'ai ajouté une nouvelle règle qui me fais passer à environ 22'' et 1 186 319 de solutions, mais j'ai encore des choses à faire avant de "publier" :)

Et Mougel, il en dit quoi de tout ça ?!
20/11/2007, 02h05
Zavonen

Citation:

Pourtant c'est très simple : si une ligne se répète p fois, tu divises par p! (et cela pour chaque groupe de lignes égales).

Oui, oui, parfaitement d'accord !
Mais tu imagines un peu le boulot en réalité.
Flaguer les solutions avec des lignes égales.
Isoler pour chacune d'elles les groupes de lignes égales
A moins qu'on puisse faire ça à la volée (dans les boucles).
Oui, finalement ça doit être possible!
Il suffit de gérer l'évènement "départ de nouvelle boucle".
J'introduis des variables f1,f2,.....f8
On ne peut s'intéresser qu'aux cas particuliers (pathologiques)
je mets ces variables à 1 lors du PREMIER tour de chaque boucle
puis à 0 dans le tour suivant.
En pratique, en début de boucle f1=(n1==n0); etc....
Quant j'ai une soluce je n'ai qu'à consulter (f1,f2,.....f8)
et ne stocker dans un fichier que les cas où il ne sont pas tous nuls, puis traiter le fichier, dans un second temps.
20/11/2007, 10h59
fremen167
Je voyais ça un peu différemment :
à chaque fois que tu as une solution ok, tu parcours tes lignes 2 à 9, et, tirant profit de l'ordre lexico, tu calcules le diviseur :
Code:

1 2 3 4 5 si ligne = précédente k = k + 1 diviseur = diviseur * k sinon k = 1
Et tu peux maintenant stocker un total des solutions :

Code:

Total = Total + 9! / diviseur

Quand tu as fini de générer toutes tes solutions, logiquement, tu dois avoir :

Code:

nombre magique = Total

Qu'en penses-tu ?
20/11/2007, 11h27
Zavonen

C'est une très bonne idée.
Je vais y réfléchir
20/11/2007, 11h32
fremen167

Citation:

Envoyé par Zavonen

C'est une (très) bonne idée, mais je vais stocker près d'un milliard d'entiers, dont la grande majorité est égale à 9!

Non, tu n'en stockes qu'un (en mémoire) ;)
20/11/2007, 11h39
Zavonen

Oui, tu as raison, mais C ne traite pas les entiers au delà du type long (sur 4 octets). Ou alors il faut que je bricole mes propres entiers longs sur 8 octets, avec une routine d'addition.
C'est faisable.

Bon, je crois que j'ai bien avancé, j'arrive à un ensemble de 40994 classes, mais il reste un problème que je ne vois pas comment résoudre.

J'ai calculé le poids d'une classe en divisant 9!^2 par un diviseur calculé de la manière suivante :
si une ligne (respectivement une colonne) se répète p fois, alors diviseur = diviseur * p!

Et oui Zanoven, vive Delphi, qui gère un type entier sur 8 octets ! :mouarf:

Ca marche bien si on ne prend en compte que les lignes ou que les colonnes, mais pas avec la combinaison des deux.

Prenons par exemple, la solution suivante :
111110000
111110000
111110000
111110000
100001111
010001111
001001111
000101111
000011111

J'arrive à un diviseur de 576 (=4! * 4!, il y a 4 lignes égales et 4 colonnes égales). Mais en fait, il existe des combinaisons de permutations lignes+colonnes qui laissent la matrice invariante. Ici, L1/L2 + C5/C6, mais aussi L2/L3 et C6/C7, etc...

Je surévalue donc le poids (ici fortement) de certaines classes.

Au final, j'obtiens un cumul des poids = 4.8 10^15, soit en gros 15 fois plus que le nombre magique.

Quelqu'un a-t-il une idée ?

Je peux récapituler les règles que j'ai imposé pour obtenir des solutions maximales si quelqu'un est intéressé.

Voici mon code (qui tourne en moins de 2 secondes :yaisse2:):

Code:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs;
 
type
  TForm1 = class(TForm)
  private
    { Déclarations privées }
  public
    { Déclarations publiques }
  end;
 
TLigne    = array[1..9] OF integer ;
TMatrice  = array[1..9] OF TLigne ;
var
  Form1   : TForm1;
  Ficsor : Text ;
  Matrice, LastMatrice : TMatrice ;
  LigneModele, SumCol, CumulLigne : TLigne ;
  Modele  : array[1..126] OF TLigne ;
  L2      : array[1..3] OF integer ;
  NumL2, IndiceModele, NumSoluce, NbMaxSoluces, L, C, Diviseur : integer ;
  Poids, Fact9Carre : comp ;
implementation
 
{$R *.DFM}
 
 
Procedure AjouterModele ;
Var Col : Integer ;
Begin
   IndiceModele := IndiceModele + 1 ;
   Modele[IndiceModele] := LigneModele ;
   Writeln('Modele n° ', IndiceModele) ;
   For Col := 1 to 9 do Write(LigneModele[Col]) ;
   Writeln ;
End ; {de Afficher}
 
 
Procedure GenererModeles(pos, restant : integer) ;
Var i : integer ;
Begin
if restant = 0
then
   begin
      for i := pos to 9 do LigneModele [i] := 0 ;
      AjouterModele ;
   end
else
   begin
   if pos + restant = 10
   then
      begin
      for i := pos to 9 do LigneModele [i] := 1 ;
      AjouterModele ;
      end
   else
      begin
      {Génération des modèles avec 1 en position pos -
       on commence par 1 pour avoir l'ordre lexicographique descendant}
      LigneModele [pos] := 1 ;
      GenererModeles(pos+1,restant-1) ;
      {Génération des modèles avec 0 en position pos}
      LigneModele [pos] := 0 ;
      GenererModeles(pos+1,restant) ;
      end
   end ;
End ; {de GenererModeles}
 
Procedure Afficher(Var Fichier : Text) ;
Var Lig, Col : integer ;
Begin
If (NumSoluce > NbMaxSoluces) and (NbMaxSoluces <> 0)
Then
   begin
   Write   ('Nombre de solution maxi atteint ') ;
   Writeln (NumSoluce, ' / ', NbMaxSoluces) ;
   Readln ;
   Halt(1) ;
   end ;
 
LastMatrice := Matrice ;
Writeln (Fichier) ;
Writeln (Fichier,'Solution n° ', NumSoluce, ' :') ;
Writeln (Fichier,'Diviseur = ', Diviseur) ;
For Lig := 1 to 9 do
   begin
   For Col := 1 to 9 do Write(Fichier, Matrice[Lig,Col]) ;
   Writeln (Fichier) ;
   end ;
End ; {de Afficher}
 
{Ajoute Modele[NumModele] en ligne NumLigne de Matrice, calcul le nombre
de 1 dans les colonnes 1 à 5 de la ligne (CumulLigne[i])
 et incrémente les cumuls par colonne correspondant}
Procedure AjouterLigne(NumLigne, NumModele : integer) ;
Var
Col : integer ;
Begin
Matrice[Numligne] := Modele[NumModele] ;
CumulLigne[NumLigne] := Matrice[NumLigne,1] +
                        Matrice[NumLigne,2] +
                        Matrice[NumLigne,3] +
                        Matrice[NumLigne,4] +
                        Matrice[NumLigne,5] ;
For Col := 1 to 9 do
  SumCol [Col] := SumCol [Col] + Modele[NumModele,Col] ;
End ; {de AjouterLigne}
 
{Décrémente les cumuls par colonne correspondant à la ligne à supprimer
 (on ne la supprime pas physiquement)}
Procedure RetirerLigne(Lig : integer) ;
Var
Col : integer ;
Begin
For Col := 1 to 9 do
  SumCol [Col] := SumCol [Col] - Matrice[Lig, Col] ;
End ; {de RetirerLigne}
 
 
Function ControleContraintes(NumLigne : integer) : boolean ;
Var Lig, Col, NbL1, NbLn, LgPref : integer ;
    Res, Encore : boolean ;
Begin
Res := true ;
 
{Règle 3 étendue++}
If CumulLigne[NumLigne] > CumulLigne[NumLigne-1]
Then Res := false
Else
  {Boucle de contrôle des cumuls de colonnes, sauf la 1ère qui par
   construction (Règle 2) est forcément OK}
  begin
  {Inutile de faire ces contrôles avant la ligne 5}
  If Numligne > 4
  Then
     begin
     Col := 2 ;
     While Res And (Col <= 9) Do
        begin
        {Plus de 5 '1' dans une colonne}
        If SumCol[Col] > 5 Then Res := False ;
     {Plus assez de ligne à créer pour avoir 5 '1' dans une colonne}
        If SumCol[Col] < NumLigne - 4 Then Res := False ;
        Inc(Col) ;
        end ;
     end ;
  end ;
  {Règle 4 étendue : Si une ligne Li contient la séquence '01' en colonne 6-7,
   ou 7-8, ou 8-9, alors on ne peut pas avoir dans les mêmes colonnes des
   lignes au dessus uniquement des couples '00' ou '11'. En pratique, on
   recherche '10' au dessus car une ligne qui aurait '01' au dessus devrait
   également respecter la règle 4. On ne contrôle pas quand CumulLigne = 5
   (car la ligne fini par 4 '0') ou 1 (elle fini par 4 '1').
   Cas particulier : la première ligne qui a 1 après la colonne 5 doit avoir :
   1..10..0 entre les colonnes 6 et 9 (sinon, on peut permuter)}
  If Res
  Then
     begin
     If ((CumulLigne[NumLigne] <> 5) AND (CumulLigne[Numligne] <> 1))
     Then
        begin
        Col := 6 ;
        {On se positionne sur la première colonne '0'}
        While Matrice [NumLigne,Col] = 1 do Inc(Col) ;
        {Le cas particulier}
        If (CumulLigne[NumLigne-1] = 5)
        Then
           begin
           {On cherche un 1 après}
           While Res and (Col <= 9) do
              if Matrice [NumLigne,Col] = 1
                 then Res := false
                 else inc(Col) ;
           end
        {Le cas général}
        Else
           begin
           {On cherche le premier 1 après, mais ce n'est pas forcément un cas
            d'erreur}
           Encore := true ;
           While Encore and (Col <= 9) do
              if Matrice [NumLigne,Col] = 1
                 then Encore := false
                 else inc(Col) ;
           {On a trouvé le 1, on vérifie les colonnes au dessus}
           If Col <= 9
           Then
              begin
              Encore := true ;
              Lig := NumLigne - 1 ;
              While Encore AND (Lig > 1) do
                 begin
                 If (Matrice [Lig,Col-1] = 1) AND (Matrice [Lig,Col] = 0)
                 Then
                    Encore := false
                 Else
                    Dec(Lig) ;
                 end ; {du while}
              If Encore Then Res := false ;
              end ;
           end ; {du cas général}
        end ;
     end ; {de règle 4 étendue}
 
  If Res
  Then
     begin
     {Règle 6}
     {On commence par compter le nombre de 1 préfixe de ligne précédente}
     Col := 1 ;
     LgPref := 0 ;
     While Matrice[NumLigne-1,Col] = 1 do
        begin
        Inc (Col) ;
        Inc (LgPref) ;
        end ;
     {Puis on vérifie que jusqu'à cette valeur, la ligne a la forme 1..10..0}
     Col := 1 ;
     While Matrice [NumLigne,Col] = 1 do Inc(Col) ;
     While Res and (Col <= LgPref) do
        if Matrice [NumLigne,Col] <> 0
           then Res := false
           else inc(Col) ;
     end ;
{Règle 5 (dédoublonnage) : Le plus grand nombre de lignes égales doit
 correspondre aux nombre de lignes de type L1 (=111110000).
 Dans le cas contraire, on pourrait par permutations obtenir une solution
 plus grande.
 On ne contrôle que la derniere ligne, puisque les précédentes l'ont déjà été.}
  If Res
  Then
     begin
     {Calcul nb de lignes L1}
     Lig := 1 ;
     NbL1 := 0 ;
     Encore := true ;
     While Encore do
        If Lig > Numligne Then Encore := False
        Else
           begin
           Col := 1 ;
           While Encore And (Col <= 9) do
              If Matrice[Lig,Col] <> Matrice[1,Col]
              Then Encore := False
              Else Inc(Col) ;
           If Encore
           Then Inc(NbL1) ;
           Inc (Lig) ;
           end;
     {Calcul du nombre de lignes = à Matrice[NumLigne]}
     Lig := NumLigne ;
     NbLn := 0 ;
     Encore := true ;
     While Encore do
        If Lig < 1 Then Encore := False
        Else
           begin
           Col := 1 ;
           While Encore And (Col <= 9) do
              If Matrice[Lig,Col] <> Matrice[NumLigne,Col]
              Then Encore := False
              Else Inc(Col) ;
           If Encore
           Then Inc(NbLn) ;
           Dec (Lig) ;
           end;
 
     If NbLn > NbL1 Then Res := False ;
     end ;
  ControleContraintes := Res ;
End ; {de ControleContraintes}
 
{Calcule le "diviseur" qui permet de calculer le cardinal d'une classe :
 cardinal = (9!)^2 / diviseur}
Function CalcDiviseur : integer ;
Var DivLig, DivCol, Facteur, Lig, Col, Col2, Entier : integer ;
    Encore, Coltriee, ToutTrie : boolean ;
    MatriceTmp : TMatrice ;
Begin
{Calcul du diviseur sur les lignes}
DivLig := 1 ;
Facteur := 1 ;
Lig := 2 ;
While Lig <= 9 do
   begin
      Encore := true ;
      Col := 1 ;
      While Encore And (Col <= 9) do
         If Matrice[Lig-1,Col] <> Matrice[Lig,Col]
         Then Encore := False {On a trouve une différence avec ligne précédente}
         Else Inc(Col) ;
      If Encore
      Then
         begin
         Facteur := Facteur + 1 ;
         DivLig := DivLig * Facteur ;
         end
      else
         Facteur := 1 ;
   Inc(Lig) ;
   end ;
{Calcul du diviseur sur les colonnes}
{Contrairement aux lignes, les colonnes ne sont pas dans l'ordre lexico
 ==> on les trie (tri à bulles dans une matrice temporaire)...}
MatriceTmp := Matrice ;
{La première colonne est la plus grande (cf. règle 2)}
Col := 2 ;
Repeat
   Col2 := 9 ;
   ToutTrie := true ;
   Repeat
      {Comparaison colonnes Col2 / Col2 -1}
      Lig := 1 ;
      Encore := true ;
      While (Lig <= 9) AND Encore do
         If MatriceTmp[Col2,Lig] = MatriceTmp [Col2-1,Lig]
         Then Inc(Lig)
         else Encore := false ;
      If Encore
      Then
         If MatriceTmp[Col2,Lig] > MatriceTmp [Col2-1,Lig]
         Then Coltriee := false
         Else Coltriee := true
      Else
         Coltriee := true ;
      If not ColTriee
      Then
         begin
         {Permutation des colonnes Col2 et Col2-1}
         Lig := 1 ;
         While Lig <= 9 do
            begin
            Entier := MatriceTmp[Col2,Lig] ;
            MatriceTmp[Col2,Lig] := MatriceTmp[Col2-1,Lig] ;
            MatriceTmp[Col2-1,Lig] := Entier ;
            Inc(Lig) ;
            end ;
         ToutTrie := false ;
         end ;
      Dec(Col2)
   until (Col2 < Col + 1) ;
   Inc(Col)
until (Col > 8) OR ToutTrie ;
 
{... puis on calcule comme pour les lignes}
DivCol := 1 ;
Facteur := 1 ;
Col := 2 ;
While Col <= 9 do
   begin
      Encore := true ;
      Lig := 1 ;
      While Encore And (Lig <= 9) do
         If MatriceTmp[Lig,Col-1] <> MatriceTmp[Lig,Col]
         Then Encore := False {On a trouve une différence avec ligne précédente}
         Else Inc(Lig) ;
      If Encore
      Then
         begin
         Facteur := Facteur + 1 ;
         DivCol := DivCol * Facteur ;
         end
      else
         Facteur := 1 ;
   Inc(Col) ;
   end ;
 
{Diviseur global}
CalcDiviseur := Divlig * DivCol ;
End ;
 
Procedure Explorer (NumLigne, NumModele : integer) ;
Var NumDeb, NumFin, i : integer ;
Begin
If ControleContraintes(NumLigne)
Then
   If NumLigne = 9
   Then
      begin
      Diviseur := CalcDiviseur ;
      Poids := Poids + (Fact9Carre / Diviseur) ;
      Inc (NumSoluce) ;
      Afficher (FicSor) ;
      end
   Else
      begin
      {Règle 2}
      If (NumLigne > 4)  And (NumModele < 71)
         Then NumDeb := 71
         Else NumDeb := NumModele  ;
 
      If NumDeb < 71
      Then NumFin := 70
      Else NumFin := 126 ;
 
      For i := NumDeb to NumFin Do
         Begin
         {Ajout à la ligne i du modèle en ligne (NumLigne + 1) de la matrice
          On incrémente aussi les totaux de colonnes}
         AjouterLigne (NumLigne + 1, i) ;
         Explorer (NumLigne + 1, i) ;
         {Retrait de la ligne (NumLigne + 1) de la matrice (il s'agit de décrémenter les totaux par colonne)}
         RetirerLigne (NumLigne + 1) ;
         End ; {du For}
      End ; {Du cas NumLigne <> 9}
{Si ControleContraintes retourne faux, inutile d'aller + loin dans cette branche}
End ;
 
Begin
{Ouverture du fichier de sortie}
AssignFile(FicSor, 'H:\TestsDelphi\SolucesMougel-01.txt') ;
Rewrite(Ficsor) ;
 
{Génération des 126 modèles de lignes dans l'ordre lexicographique descendant}
IndiceModele := 0 ;
GenererModeles(1,5) ;
 
{Règle 1}
AjouterLigne(1,1) ;
 
{Stockage des numéros de modèle des lignes 2 possibles - cf. Règle 4}
L2[1] := 1;
L2[2] := 2;
L2[3] := 6;
 
{Factorielle 9}
Fact9Carre := 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 ;
Fact9Carre := Fact9Carre * Fact9Carre ;
 
{Demande du nombre maxi de solutions}
Write('Combien de solutions maximums ?') ;
Readln (NbMaxSoluces) ;
 
{Règle 4}
For NumL2 := 1 to 3 Do
   Begin
   AjouterLigne(2,L2[NumL2]) ;
   Explorer(2,L2[NumL2]);
   RetirerLigne(2) ;
   End ;
{Fermeture du fichier de sortie}
Writeln (FicSor,'Fin des solutions') ;
Writeln (FicSor,'Nombre total de solutions pondéré : ', Poids) ;
Close(Ficsor) ;
 
Writeln ('Fin des solutions') ;
Writeln ('Dernière solution obtenue : (N°', NumSoluce, ')') ;
Writeln ('Nombre total de solutions pondéré : ', Poids) ;
Matrice := LastMatrice ;
Afficher(Output);
(*For L := 1 to 9 do
   begin
   For C := 1 to 9 do Write(LastMatrice[L,C]) ;
   Writeln ;
   end ;*)
Readln ;
Halt (2) ;
End.

Je vois avec plaisir que tu avances.
Je n'ai pas (encore) de solutions à te proposer.
Tout d'abord je ne suis pas suffisamment 'rentré' dans ton code, bien qu'il soit maintenant bien documenté.
Ensuite, j'avais commencé à essayer de prendre le problème comme toi, mais j'ai abandonné (peut être à tort), j'ai aussi buté sur le pb de l'interférence des permutations des lignes et des colonnes.
C'est pourquoi je me suis résolu à essayer la 'force brute'.
Tout est près pour un essai cette nuit.
J'ai donc rajouté quelques lignes de code:

Code:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
unsigned int terme (unsigned char s[9])
{
    unsigned int d=1;
    unsigned int i;
    unsigned int k=1;
    for (i=1;i<9;i++)
    {
        if (s[i]==s[i-1])
        {
            k++;
            d*=k;
        }
        else
            k=1;
    }
    return 362880/d;
}
 
typedef struct
{
    unsigned int low;
    unsigned int high;
}BigInt;
 
void ajoute (BigInt *pBI , unsigned int ui)
{
    pBI->low+=ui;
    if (pBI->low >= 1000000000)
    {
        pBI->high +=1;
        pBI->low -=1000000000;
    }
}
void Recherche()
{
    unsigned char n0,n1,n2,n3,n4,n5,n6,n7,n8;
    unsigned int nbsol=0;
    unsigned char sc0[9],sc1[9],sc2[9],sc3[9],sc4[9],sc5[9],sc6[9],sc7[9],sc8[9];
    unsigned char sci[9]={0,0,0,0,0,0,0,0,0};
    unsigned char sol[9];
    unsigned int term;
    BigInt MAGIC;
    MAGIC.low=MAGIC.high=0;
    for (n0=0;n0<53;n0++)
    {
        printf("%d/53\n",n0);
        add(sci,sc0,n0);
        for (n1=n0;n1<54;n1++)
        {
            add(sc0,sc1,n1);
            for (n2=n1;n2<55;n2++)
            {
                add(sc1,sc2,n2);
                for (n3=n2;n3<56;n3++)
                {
                    add(sc2,sc3,n3);
                    for (n4=n3;n4<126;n4++)
                    {
                        if (test2(sc3,n4,5))
                        {
                            add(sc3,sc4,n4);
                            for (n5=n4;n5<126;n5++)
                            {
                                if (test2(sc4,n5,6)&&test1(sc4,n5))
                                {
                                    add(sc4,sc5,n5);
                                    for (n6=n5;n6<126;n6++)
                                    {
                                        if (test2(sc5,n6,7)&&test1(sc5,n6))
                                        {
                                            add(sc5,sc6,n6);
                                            for (n7=n6;n7<126;n7++)
                                            {
                                                if (test2(sc6,n7,8)&&test1(sc6,n7))
                                                {
                                                    add(sc6,sc7,n7);
                                                    for (n8=n7;n8<126;n8++)
                                                    {
                                                        if (test2(sc7,n8,9)&&test1(sc7,n8))
                                                        {
                                                            nbsol++;
                                                            sol[0]=n0;
                                                            sol[1]=n1;
                                                            sol[2]=n2;
                                                            sol[3]=n3;
                                                            sol[4]=n4;
                                                            sol[5]=n5;
                                                            sol[6]=n6;
                                                            sol[7]=n7;
                                                            sol[8]=n8;
                                                            term=terme(sol);
                                                            ajoute(&MAGIC,term);
 
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
 
                            }
                        }
                    }
 
                }
            }
        }
 
    }
    printf ("%d\n",nbsol);
    printf("%u\n",MAGIC.low);
    printf("%u\n",MAGIC.high);
}

21/11/2007, 10h25
Zavonen

C'est raté !

Valeur trouvée: 314783498302560
Je vais essayer de trouver la raison de cet écart.
21/11/2007, 10h32
pseudocode

Citation:

Envoyé par Zavonen

Valeur trouvée: 314783498302560
Je vais essayer de trouver la raison de cet écart.

bof, on n'est pas à 0.2 billion près... :aie:
21/11/2007, 12h06
Zavonen

Citation:

bof, on n'est pas à 0.2 billion près.

Cela a été ma première réaction. Mais bon, dommage d'échouer si près du but.
J'ai revu mon programme, sans rien trouver. Il devrait marcher car il est très 'rustique'.Pas facile de faire des tests pour déboguer avec un truc aussi long à exécuter, et cette fois, je ne vois plus du tout comment l'accélérer.
21/11/2007, 14h55
fremen167

Salut Zanoven,

Bravo, tu es vraiment près du but !

J'ai jeté un coup d'oeil sur le code que tu as ajouté, et je me pose deux questions qui pourraient (peut-être, pour la première) te permettre de finir et (certainement, pour la seconde) d'améliorer tes performances :

1) pour n0, tu t'arrêtes à 53, puis 54 pour n1... et 56 pour n3. Sauf erreur de ma part, le max de n3 est 69 (ce qui correspond à 70 en Pascal dans mon programme), non ?
2) Pour n4, tu pars systématiquement de n3, mais en fait, ne faut-il pas partir de 70 ?

Je vais regarder tout ça de plus près. En attendant, je publie la dernière version documentée 'nightly build' ;).
Peut être quelqu'un verra-t-il immédiatement le 'bug'.

Code:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <stdio.h>
#include <stdlib.h>
 
// tableau des 126 lignes possibles
unsigned int possibles[126];
// décomposition binaire de chacune des possibilités
unsigned char digits[126][9];
 
// Accès aux chiffres binaires
unsigned char Digit(unsigned int i,unsigned int n)
{
    unsigned int k;
    for (k=0;k<i;k++) n/=2;
    return n%2;
}
 
// calcule le nombre de chiffres de n en binaire
int NumberDigits(unsigned int n)
{
    if (n==1) return 1;
    else
        return (n%2)+NumberDigits(n/2);
}
 
// détermine si la représentation binaire d'un entier
// comporte 5 fois le chiffre 1
int Has5Digits(unsigned int n)
{
    return NumberDigits(n)==5;
}
 
// initialise le tableau des 126 possibles pour les lignes
void FillPossibles()
{
    int i,j;
    for (i=1,j=0;i<512;i++)
        if (Has5Digits(i))
            possibles[j++]= i;
    for (i=0;i<126;i++)
        for (j=0;j<9;j++)
            digits[i][j]=Digit(j,possibles[i]);
}
 
// test pour voir si le total d'une colonne dépasse 5
int test1 (unsigned char scol[9], unsigned char n)
{
    int i;
    for (i=0;i<9;i++)
    {
        if (scol[i]+digits[n][i]>5)
            return 0;
    }
    return 1;
}
 
// test pour voir si le total d'une colonne est au niveau d
// insufisant pour pouvoir atteindre 5  à la neuvième ligne 
int test2 (unsigned char scol[9], unsigned char n, unsigned char d)
{
    int i;
    for (i=0;i<9;i++)
    {
        if (scol[i]+digits[n][i]+9-d<5)
            return 0;
    }
    return 1;
}
 
// ajoute la décomposition binaire de n à sc, résultat dans r
void add( unsigned char sc[9],unsigned char r[9], unsigned char n)
{
    int i;
    for (i=0;i<9;i++)
    {
        r[i]=sc[i]+digits[n][i];
    }
}
 
// le paramètre s est une solution triée
// calcule le nombre de solutions engendrées par s
// par permutation de ses lignes
unsigned int terme (unsigned char s[9])
{
    unsigned int d=1;
    unsigned int i;
    unsigned int k=1;
    for (i=1;i<9;i++)
    {
        if (s[i]==s[i-1])
        {
            k++;
            d*=k;
        }
        else
            k=1;
    }
    return 362880/d;
}
 
/*** Imlémentation minimum d'entiers à 18 chiffres pour notre pb****/
typedef struct
{
    unsigned int low;
    unsigned int high;
}BigInt;
 
// ajouter un entier à un BigInt
void ajoute (BigInt *pBI , unsigned int ui)
{
    pBI->low+=ui;
    if (pBI->low >= 1000000000)
    {
        pBI->high +=1;
        pBI->low -=1000000000;
    }
}
/********************************************************/
// la fonction itérative de recherche qui fait le travail
void Recherche()
{
    unsigned char n0,n1,n2,n3,n4,n5,n6,n7,n8;
    unsigned int nbsol=0;
    unsigned char sc0[9],sc1[9],sc2[9],sc3[9],sc4[9],sc5[9],sc6[9],sc7[9];
    unsigned char sci[9]={0,0,0,0,0,0,0,0,0};
    unsigned char sol[9];
    unsigned int term;
    BigInt MAGIC;
    MAGIC.low=MAGIC.high=0;
    for (n0=0;n0<53;n0++)
    {
        printf("%d/53\n",n0);
        add(sci,sc0,n0);
        for (n1=n0;n1<54;n1++)
        {
            add(sc0,sc1,n1);
            for (n2=n1;n2<55;n2++)
            {
                add(sc1,sc2,n2);
                for (n3=n2;n3<56;n3++)
                {
                    add(sc2,sc3,n3);
                    for (n4=n3;n4<126;n4++)
                    {
                        if (test2(sc3,n4,5))
                        {
                            add(sc3,sc4,n4);
                            for (n5=n4;n5<126;n5++)
                            {
                                if (test2(sc4,n5,6)&&test1(sc4,n5))
                                {
                                    add(sc4,sc5,n5);
                                    for (n6=n5;n6<126;n6++)
                                    {
                                        if (test2(sc5,n6,7)&&test1(sc5,n6))
                                        {
                                            add(sc5,sc6,n6);
                                            for (n7=n6;n7<126;n7++)
                                            {
                                                if (test2(sc6,n7,8)&&test1(sc6,n7))
                                                {
                                                    add(sc6,sc7,n7);
                                                    for (n8=n7;n8<126;n8++)
                                                    {
                                                        if (test2(sc7,n8,9)&&test1(sc7,n8))
                                                        {
                                                            nbsol++; // incrémenter le nombre de solutions triées
                                                            sol[0]=n0;
                                                            sol[1]=n1;
                                                            sol[2]=n2;
                                                            sol[3]=n3;
                                                            sol[4]=n4;
                                                            sol[5]=n5;
                                                            sol[6]=n6;
                                                            sol[7]=n7;
                                                            sol[8]=n8;
															// nbre de solutions distinctes engendrées par permutations des lignes de sol
                                                            term=terme(sol);
                                                            ajoute(&MAGIC,term); // cumul
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf ("%d\n",nbsol); // afficher le nombre de solutions triées.
    printf("%u\n",MAGIC.low); // afficher le nombre total
    printf("%u\n",MAGIC.high);
}
// fonction principale
int main()
{
    FillPossibles();
    Recherche();
    system("Pause");
    return 0;
}

21/11/2007, 15h11
Zavonen

Citation:

1) pour n0, tu t'arrêtes à 53, puis 54 pour n1... et 56 pour n3. Sauf erreur de ma part, le max de n3 est 69 (ce qui correspond à 70 en Pascal dans mon programme), non ?
2) Pour n4, tu pars systématiquement de n3, mais en fait, ne faut-il pas partir de 70 ?

Tu l'as peut être déjà fait:
Imprime sur chaque ligne
-i - possibles[i] - tous les digits[i][j] j entre 0 et 9
Tu verras alors clairement la raison de mes choix de bornes.
21/11/2007, 17h35
fremen167

Citation:

Envoyé par Zavonen

Tu verras alors clairement la raison de mes choix de bornes.

Je ne vois pas. J'ai :
53 - 242 - 011110010
54 - 244 - 011110100
55 - 248 - 011111000
56 - 271 - 100001111
(je n'ai pas compilé ton code, en fait je n'ai pas de compilateur C sous la main, mais j'ai simulé ta fonction par Excel).
21/11/2007, 17h38
Zavonen

Je suis d'accord avec toi mais j'écris les représentations binaires de droite à gauche, donc j'ai les mêmes séquences mais inversées:
21/11/2007, 17h52
fremen167

Mais dans ce cas, les lignes ne sont pas triées selon l'ordre lexicographique, mais selon l'ordre du nombre dont ils sont la représentation inversée...

Et je ne vois pas mieux... peux-tu m'expliquer ?
21/11/2007, 18h47
Zavonen

L'ordre lexicographique ne joue aucun rôle particulier, il peut être remplacé par n'importe quel autre (à une permutation près).
21/11/2007, 18h57
fremen167

Citation:

Envoyé par Zavonen

L'ordre lexicographique ne joue aucun rôle particulier, il peut être remplacé par n'importe quel autre (à une permutation près).

Oui, ça d'accord, mais pourquoi les valeurs 53 etc. ? C'est ça que je ne comprend pas !
21/11/2007, 19h00
Zavonen

parce que dans mon classement, à partir de 56, je n'ai que des 1 en dernière position. Comme il faut choisir 9 lignes le total de la dernière colonne dépassera forcément 5.

Voir 40 message(s) de cette discussion en une page