Demande d'aide pour élaborer un algo pour un pb simple mais long
Bonjour,
Je recherche toutes les matrices 9x9 comportant 5 fois le nombre 1 dans chaque ligne et dans chaque colonne (tous les autres éléments de la matrice sont nuls).
Je ne sais programmer qu'en VBA et je ne m'en sors pas. Non seulement mon algorithme semblent durer indéfiniment, mais de plus je ne suis pas sûr qu'il soit correct.
Ce problème vous semble-t-il facile?
Quelqu'un pourrait-il m'indiquer des pistes?
Merci par avance pour vos réponses...
Edit: le nb 1 doit apparaître 5 fois exactement dans chaque ligne et chaque colonne
Proposition d'algo simple
Voici en pseudo Pascal l'implémentation des règles que je propose.
Le traitement utilise les données suivantes (variables globales):
Code:
1
2
3
4
5
|
matrice (1:9; 1:9) : 1 matrice 9 * * pour stocker l'état du tableau
modele (1:126 ; 1;9) : 1 tableau des lignes "modèles" (les 126)
L2 : 1 tableau des indices des 5 lignes L2 possibles |
Le code des principaux traitements est le suivant :
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
|
Procedure Explorer (num-ligne, num-modele : int) ;
Var num-deb, num-fin : integer ;
Begin
If Controle-contraintes(num-ligne)
Then
If num-ligne = 9
Then afficher
Else
{Règle 2}
IF num-ligne > 5
Then num-deb = max (71, num-modele)
Else num-deb = num-modele
End-if
If num-deb < 71
Then num-fin = 70
Else num-fin = 126
End-if
FOR 1 := num-deb to num-fin DO
Begin
{Ajout de la ligne i de modèle en ligne (num-ligne + 1) de la matrice
On incrémente aussi les totaux de colonnes}
Ajouter (num-ligne + 1, i) ;
Explorer (num-ligne + 1, i) ;
{Retrait de la ligne (num-ligne + 1) de la matrice (il s'agit de décrémenter les totaux par colonne)}
Retirer (num-ligne + 1) ;
End
End-if
{Si controle-contraintes retourne faux, inutile d'aller + loin dans cette branche}
End ;
Function Controle-contrainte (num-ligne : integer) : boolean ;
Var lig, col, Cumul-ligne : integer ;
res : boolean ;
Begin
Res := true ;
Cumul-ligne := Matrice(num-ligne,2) + Matrice (num-ligne,3) + Matrice(num-ligne,4) + Matrice (num-ligne,5)
{Règle 3 étendue}
If Cumul-ligne > Cumul-L2
Then res := false
Else
{Boucle de contrôle des cumuls de colonnes}
End-if ;
Controle-contrainte := Res ;
End ; {de controle-contrainte}
Main ;
Begin
{Génération des 126 modèles de lignes dans l'ordre lexicographique descendant -
Stocke également dans L2(1:5) les indices des 5 lignes 2 possibles - cf Règle 4}
Generer-modeles ;
{Règle 1}
Ajouter (1, 1) ;
{Règle 4}
For i := 1 to 5
Begin
Ajouter (2, L2(i)) ;
cumul-L2 = Matrice(2,2) + Matrice (2,3) + Matrice(2,4) + Matrice (2,5)
Explorer (2, L2(i)) ;
Retirer (2) ;
End ;
End. |
On peut remplacer Afficher par la gestion des permutations d'une matrice génératrice (évidemment, là, on dégrade fortement les perfs, et pour les maintenir il faudrait peut-être arriver à générer ces permutations dans l'ordre lexicographique, mais je ne vois pas comment de prime abord :?).
Mougel, est-ce que ça peut répondre à ton besoin ?
