Discussion :

[IME14]

Bonjour

Je cherche à résoudre le problème suivant :

Objectif :

Générer une matrice M de dimensions 29×8 où :
Chaque ligne de la matrice est un sous-ensemble de 8 entiers distincts choisis parmi les entiers de 1 à 29.
Chaque paire de lignes de la matrice doit partager exactement deux éléments en commun.

Contraintes :

Chaque ligne doit contenir 8 valeurs distinctes.
Chaque paire de lignes doit avoir exactement deux éléments en commun.
La solution doit utiliser uniquement les valeurs de 1 à 29.

Sortie attendue :

Une matrice 29×8 respectant les contraintes ou un message indiquant qu'aucune solution n'existe.

Ce que je demande :
Je souhaite obtenir :

- Un code Python ou dans tout autre langage qui peut générer une solution rapidement.
- Si vous connaissez une solution algorithmique ou théorique à ce problème, je serais heureux que vous la partagiez.

Pour info j'ai trouvé la solution pour une matrice de dimensions 16×6 mais le code il se bloque au niveau de 29*8


Voici le code python qui génère une matrice de dimensions 16×6 avec les contraintes suivantes :

1-Chaque ligne contient 6 valeurs distinctes.
2-Chaque paire de lignes partage exactement 2 éléments.
3-Les valeurs utilisées sont comprises entre 1 et 16.

Cependant, lorsqu'on essaie d'étendre ce code pour générer une matrice de 29×8 en utilisant les valeurs de 1 à 29, le code n'arrive pas à trouver une solution valide.
--------------

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
28
29
30
31
32
33
import random
import pandas as pd
 
# Définition des paramètres
C = list(range(1, 17))
NUM_ROWS = 16
NUM_COLS = 6
 
# Initialisation de la matrice vide
matrix = []
 
# Fonction pour vérifier les contraintes de chevauchement
def has_valid_overlap(new_row, matrix):
    for row in matrix:
        # Calculer le nombre d'éléments communs avec chaque ligne existante
        common_elements = set(new_row) & set(row)
        # Vérifie qu'il y a exactement 2 éléments en commun
        if len(common_elements) != 2:
            return False
    return True
 
# Génération de la matrice ligne par ligne
while len(matrix) < NUM_ROWS:
    # Générer une ligne aléatoire avec 6 valeurs uniques de C
    new_row = random.sample(C, NUM_COLS)
    # Vérifier les contraintes de chevauchement avec les lignes existantes
    if has_valid_overlap(new_row, matrix):
        matrix.append(new_row)
 
# Conversion de la matrice en DataFrame
df = pd.DataFrame(matrix, columns=[f'Col_{i+1}' for i in range(NUM_COLS)])
 
# Afficher la matrice sous forme de DataFrame

df


Merci

[tbc92]

Si je ne m'abuse, tu procèdes ainsi :
J'ai ajouté les instructions Print(new_row) et print(len(matrix) juste après l'instruction matrix.append(new_row) pour voir ce qui ce passe.
Je prends une première ligne, au hasard ; par exemple 1,2,3,4,5,6,7,8 (je prends cet exemple un peu particulier, ce sera plus facile à suivre)
Puis tu cherches une 2ème ligne, tu fais autant d'essais que nécessaire, jusqu'à trouver une ligne qui convient. Admettons que la premère ligne sur laquelle tu tombes soit 7,8,9,10,11,12,13,14
Puis tu cherches une 3ème ligne, tu fais autant d'essais que nécessaire, jusqu'à trouver une ligne qui convient. Admettons que la premère ligne sur laquelle tu tombes soit 7,8,13,14,15,16,17,18
Puis tu cherches une 4ème ligne, tu fais autant d'essais que nécessaire, jusqu'à trouver une ligne qui convient. Admettons que la premère ligne sur laquelle tu tombes soit 1,2,9,10,15,16,19,20
Puis tu cherches une 5ème ligne, tu fais autant d'essais que nécessaire, jusqu'à trouver une ligne qui convient. Admettons que la premère ligne sur laquelle tu tombes soit 1,2,11,12,17,18,21,22
etc
A un moment, tu peux avoir fait des mauvais choix (tu n'y es pour rien, tu utilises la fonction random) , et tu peux te retrouver dans une impasse ; peut-être que les 20 premières lignes trouvées font qu'il n'y a plus de solution pour une 21 ème ligne. Et tu n'as aucun processus de retour en arrière, tu n'as rien pour dire : la ligne n°20 crée un blocage, cherchons-en une autre pour voir si ça va mieux. Ton programme cherche une 21ème ligne, longtemps, indéfiniment même parce que peut-être qu'il n'y a plus aucune solution.
Et si il finit par tomber juste, il va falloir être méga chanceux avant de trouver une 22ème ligne, parce que les contraintes seront encore plus fortes.
Sur les essais que j'ai faits, il trouve les 10 premières lignes quasi instantanément.... puis ça galère , plusieurs minutes que j'attends, et je n'ai toujours rien pour la 15ème ligne, et on est encore très loin de 29.

Dans toutes ces questions de combinatoire, il faut un processus de retour en arrière, et il faut éviter la fonction random()
Ou, à défaut de processus de retour en arrière, à chaque étape, il faut recenser toutes les lignes compatibles, mais en enlevant celles qui font visiblement doublon.

Pour la première ligne, je prends (1,2,3,4,5,6,7,8) ;
Pour la deuxième ligne, je prends (1,2,9,10,11,12,13,14) ; Toutes les autres hypothèses font doublon.
Pour la 3ème, j'ai quelques choix, mais très peu : (1,2,15,16,17,18,19,20) ou bien (1,3,9,15,16,17,18,19) ou bien (3,4,9,10,15,16,17,18). C'est tout (sauf oubli ???)
etc.

Si on ne veut pas de cette solution 'sur mesure', puisque la première ligne est imposée, on peut appliquer ce processus. Et à la fin, on applique une permutation : 1-->x 2-->b, 3-->t ... chaque n° correspond à un élément, mais pas forcément avec la numérotation 'logique'.

[tbc92]

Le challenge m'a amusé.
J'ai fait une recherche exhaustive (ça tourne, c'est long), mais c'est à peu près certain qu'il n'y a pas de solution avec 29 lignes.
Pour l'instant, le meilleur résultat trouvé contient 17 lignes, et sur cette base de 17 lignes, aucune ligne n'est compatible, pas de possibilité de monter à 18.
Comme je disais dans le précédent message, peut-être que j'ai mal choisi ces 17 lignes ... mais déjà, je suis presque surpris d'arriver à 17 lignes. A partir de 13 ou 14 lignes, j'ai très souvent des blocages.
On peut regarder ça en terme probabiliste.
Choisir 8 nombres parmi 29, il y a 4292145 possibilités.
Quand j'ai choisi une ligne de 8 nombres, combien de choix sont valides pour une 2ème ligne ? Il reste 1519392 lignes, à peu près 3 fois moins.
Quand j'ai choisi cette 2ème ligne, combien de choix sont valides pour une 3ème ligne ? il reste 420238 lignes , à peu près 3.6 fois moins.
Si on se base là dessus, si on dit qu'à chaque ligne, l'univers des lignes compatibles est divisé par 3, on retombe sur le même résultat, on arrive à un blocage vers la 14ème ligne.

La solution avec 17 lignes (les éléments sont numérotés de 11 à 39, et pas de 1 à 29...) :

11:12:13:14:15:16:17:18:
11:12:19:20:21:22:23:24:
11:13:19:25:26:27:28:29:
12:14:19:25:30:31:32:33:
13:15:20:21:25:30:34:35:
14:15:22:23:26:27:30:36:
16:17:20:22:25:28:31:36:
12:13:22:29:32:34:36:37:
11:15:23:28:31:33:34:37:
11:18:20:26:32:33:35:36:
12:15:20:27:28:32:38:39:
12:16:24:26:28:30:35:37:
13:14:21:24:28:33:36:38:
14:17:19:20:26:34:37:38:
15:17:21:24:26:29:31:32:
15:16:19:22:29:33:35:38:
15:18:19:24:25:36:37:39:

[tbc92]

J'ai fait quelques changements dans le programme, pour optimiser.
En quelques minutes, il trouve une solution pour 16 lignes ; puis au bout de plus d'une heure, il trouve une solution pour 17 lignes et juste après, 18 lignes, ... et depuis quelques heures... il cherche et cherche, mais pas mieux que 18 lignes.

La solution trouvée pour 18 lignes :

11:12:13:14:15:16:17:18:
11:12:19:20:21:22:23:24:
11:12:25:26:27:28:29:30:
11:13:19:25:31:32:33:34:
11:14:20:26:31:35:36:37:
11:15:21:27:32:35:38:39:
12:13:22:28:31:36:38:39:
12:16:20:29:33:34:35:38:
12:17:23:27:32:33:36:37:
13:14:21:23:28:30:33:35:
13:15:20:23:25:29:37:39:
13:16:21:22:26:27:34:37:
13:17:20:24:26:30:32:38:
13:18:19:24:27:29:35:36:
14:16:23:24:25:27:31:38:
14:17:19:20:27:28:34:39:
15:18:20:22:27:30:31:33:
16:18:20:21:25:28:32:36:

[IME14]

Vous m'avez vraiment surpris, car je n'arrive pas à dépasser 13 lignes dans ce contexte. Cependant, je peux ajouter quelques observations intéressantes :

Si la matrice est correctement construite, chaque valeur apparaît exactement 8 fois dans l'ensemble des lignes.
De plus, chaque paire de valeurs présentes dans une ligne apparaît exactement deux fois dans l'ensemble des lignes.

aussi
La matrice se présente sous la forme

1 2 3 4 5 6 7 8
1 2
1 3
⋅⋅⋅
⋅⋅⋅
6 7
6 8
7 8

Ces propriétés montrent une structure particulièrement bien équilibrée et peuvent être très utiles pour valider ou optimiser le programme.

[tbc92]

Vous m'avez vraiment surpris, car je n'arrive pas à dépasser 13 lignes dans ce contexte.

Oui, et je t'ai expliqué pourquoi tu n'arrives pas à dépasser 13.

Si la matrice est correctement construite, chaque valeur apparaît exactement 8 fois dans l'ensemble des lignes.

Affirmation un peu rapide, basée sur quoi ?

[IME14]

Affirmation un peu rapide, basée sur quoi ?

l'affirmation est basée sur "balanced incomplete block design" (BIBD)

Un BIBD doit respecter les trois conditions suivantes :

1. Chaque bloc contient exactement kkk éléments.
2. Chaque élément appartient exactement à rrr blocs.
3. Chaque paire d'éléments apparaît exactement dans λ\lambdaλ blocs.

avec

• v=29 (valeurs 1 à 29),
• b=29 (lignes de la matrice),
• k=8 (valeurs dans chaque ligne),
• r=8 (chaque valeur apparaît dans 8 lignes),
• λ=2 (chaque paire apparaît exactement 2 fois).

Vérification des Équations fondamentales d'un BIBD:

1. b⋅k=v⋅r => 29*8=29*8
2. λ⋅(v−1)=r⋅(k−1) => 2⋅(29−1)=8⋅(8−1)

Tout est vérifié, donc cette configuration respecte les équations du BIBD.

[Guesset]

Bonjour,

Une question? Quand on dit deux lignes quelconques doivent avoir deux valeurs en commun, cela signifie-t-il à la même place dans chacune des lignes ? Ou peuvent elles être en commun alors qu'elles n'ont pas la même position dans chacune des lignes ?

Illustration : 1,2,3,4,5,6,7,8 et 2,1,9,10,11,12,13,14 ont 0 ou 2 valeurs en commun ?

Salutations

[IME14]

Une question? Quand on dit deux lignes quelconques doivent avoir deux valeurs en commun, cela signifie-t-il à la même place dans chacune des lignes ? Ou peuvent elles être en commun alors qu'elles n'ont pas la même position dans chacune des lignes ?

Lorsque nous disons que deux lignes quelconques doivent avoir deux valeurs en commun, cela signifie simplement que les deux lignes partagent exactement deux éléments identiques, indépendamment de leurs positions dans les lignes.
En d'autres termes, les positions des valeurs communes n'ont pas d'importance.

[tbc92]

@Guesset,
dans ma compréhension, l'ordre n'intervient pas.
En gros, on a une matrice avec 29 colonnes et idéalement 29 lignes. Dans cette matrice, on a uniquement des 1 et des 0. On a 8 fois le chiffre 1 sur chaque ligne.... et d'après les dernières informations, on aurait aussi 8 fois le chiffre 1 sur chaque colonne.
Et le 'produit scalaire' de 2 lignes serait systématiquement égal à 2. (Idem le produit scalaire entre 2 colonnes d'après les dernières informations).

@IME14
Par rapport à la demande initiale, tu ajoutes des contraintes , la question n'est plus la même. Peu importe... mais déjà, sans ces contraintes supplémentaires, c'est à peu près certain qu'il n'y avait pas de solution.
Tu donnes 2 équations, et tu dis que les nombres (v=29,b=29,k=8,r=8,lambda=2) vérifient bien les équations 'caractéristiques' d'un BIBD.
Certes.
Mais si on lit la page Wikipédia (en Français), on nous dit clairement que même si on a des nombres (v,b,k,r,lambda) qui vérifient ces 2 équations, ces 2 conditions ne sont pas suffisantes, on n'a absolument pas l'assurance qu'il existe une solution.

[Guesset]

Bonjour,

La question que je pose est effectivement de savoir si c'est un problème de matrices (différenciée par la distribution indicée des valeurs - ex. la matrice identité a les mêmes valeurs mais se distingue d'une matrice de permutation) ou un problème d'ensemble donc avec seulement des notions d'appartenances ce qui semble l'interprétation de tbc92 (les 1 et les 0 cités étant les témoins d'appartenance).

Cette deuxième approche est vraisemblablement la bonne (sinon il n'y a pas de réel problème ), mais l'expression du problème fait état de matrices d'où un besoin de confirmation.

Salutations

[tbc92]

C'est certain que c'est cette interprétation.
Le morceau de code Python proposé par IME14 au début va totalement dans ce sens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 common_elements = set(new_row) & set(row)
        # Vérifie qu'il y a exactement 2 éléments en commun
        if len(common_elements) != 2:
            return False

[Guesset]

Bonjour,

L'approche ensembliste a quelques avantages.

Ainsi la solution est une collection d'ensembles (espérons 29) avec des recouvrements de 2 éléments par couple d'ensemble. Ce n'est pas nouveau.

Mais pour des ensembles, l'identification des élément (l'ordre) importe peu. Comme il est possible de faire une bijection des 29 vers un autre arrangement de 29 conservant pleinement la solution, il est possible de réintroduire des contraintes d'ordre. Cela diminue fortement l'éventail des cas à étudier. Par exemple, fixer la règle d'augmentation de la croissance de consommation des éléments : commencer par les plus petits et faire une croissance compacte. Les deux premières étapes sont ainsi uniques :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
1 : ******** -------- -------- -----
2 : **------ ******-- -------- ----

La première étape divise par 4 292 145 le nombre de cas d'une analyse brute, la seconde par 1 519 392 (6.5 10¹² pour les deux). Par la suite c'est plus difficile mais l'ordre imposé continue de diviser les cas.

Par exemple, la 3e partition ne présente que 3 variantes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
3a : **------ -------- ******-- -----
3b : *-*----- *------- *****--- ----
3b : --**---- **------ ****---- ----

Cela peut paraître étrange de réintroduire de l'ordre là où on peut s'en passer mais le but n'est pas tant de trouver une solution de rang maxi que de connaître ce rang. Si vraiment on y tient, il est toujours possible de générer les 29! solutions équivalentes

Il peut paraître un peu contre-intuitif qu'une bijection conserve les solutions. Quelques manipulations sur un volume réduit aide à s'en convaincre.

Pour l'instant, je n'ai codé qu'un outil de manipulation manuel qui permet de jouer avec ces contraintes. Avec un peu de courage et de temps, une recherche automatique pourrait apparaître

Salutations

[tbc92]

J'arrivais à la même conclusion, avec les mêmes résultats pour les lignes 1 et 2, les 3 mêmes options pour la ligne 3. ( cf ma toute première réponse).
Ensuite, je me suis attaqué à la programmation.
On trouve dans un temps raisonnable une solution jusqu'à 18 lignes. Mais même en continuant plusieurs heures, impossible de trouver une solution avec 19 lignes. Donc franchement peu d'espoir de trouver une solution avec 29 lignes.

IME14 parle de BIBD. J'ai trouvé ceci : https://www.researchgate.net/publica..._trivial_BIBDs

J'ai lu en 15 secondes, c'est certainement trop superficiel comme lecture. On y trouve un recensement de tailles pour lesquelles il y a des BIBDs valides, et pas de solution pour v=29

Mais la demande n'est pas très claire. Dans le tout premier message, on a une demande 'générale', puis IME14 parle de BIBD, et donc de contraintes supplémentaires.

[IME14]

Bonjour,

Mais la demande n'est pas très claire. Dans le tout premier message, on a une demande 'générale', puis IME14 parle de BIBD, et donc de contraintes supplémentaires.

la demande est tjr la même :

Générer une matrice M de dimensions 29×8 où :
- Chaque ligne de la matrice représente un sous-ensemble de 8 entiers distincts, choisis parmi les entiers de 1 à 29.
- Chaque paire de lignes doit avoir exactement deux éléments en commun.

Avec la résolution des matrices de dimensions 16×6..., j’ai remarqué que :
- Si la matrice est correctement construite, chaque valeur apparaît exactement n fois dans l’ensemble des lignes (par exemple, n = 6 pour une matrice 16×6...).
- De plus, chaque paire de valeurs présentes dans une ligne apparaît exactement deux fois dans l’ensemble des lignes.

Ces observations peuvent être utilisées comme des contraintes pour réduire l’ensemble des solutions possibles et ainsi optimiser l’algorithme de génération.

IME14 parle de BIBD. J'ai trouvé ceci : https://www.researchgate.net/publica..._trivial_BIBDs

Il s'agit simplement d'une recherche dans la littérature afin de trouver une véritable reformulation mathématique de ce type de problème, bien que cela ne corresponde pas exactement au cas étudié.

Merci à vous

[tbc92]

Dans le cas 16 lignes, avec des nombres entre 1 et 16, et 6 nombres par lignes, tu as remarqué que chaque valeur apparaît exactement sur 6 lignes.
Ok.
Tu en déduis que dans le cas de 29 lignes, avec des nombres entre 1 et 29, 8 colonnes et 2 éléments en commun entre 2 lignes, on aurait le même constat, chaque nombre apparaîtrait exactement 8 fois.
Et donc tu suggères d'exploiter cette propriété pour aller plus vite.
Ok.
On pourrait donc modifier le programme et dire : si tel nombre a déjà été utilisé 8 fois, alors on n'a plus le droit de l'utiliser dans les lignes suivantes.
Mais ici, le problème n'est pas qu'une histoire de vitesse de traitement.
On a fortement l'impression qu'il n'y a pas de solution.
Les meilleurs solutions trouvées ont 18 lignes, on est loin des 29 lignes de l'objectif. Et ces solutions auraient été éliminées si on avait appliqué tes contraintes.
Si on ajoute ces 'optimisations', les meilleures solutions trouvées ont aussi 18 lignes, mais c'est presque chanceux ! En ajoutant des contraintes, certes on conclue plus vite, mais on risque d'éliminer des solutions.

Si avec ces 'optimisations', le programme va vite, et arrive à la conclusion : au mieux, on arrive à 18 lignes, que peut-on en conclure ?
Rien.

[Guesset]

Bonjour,

En regardant la solution de TBC92, je m'étais demandé l'influence de la dispersion des taux d'usage des positions : quelques 8 et beaucoup de 4 et 5.

J'ai tendance à penser que cela devrait être plus homogène pour pouvoir espérer continuer un peu. Cette homogénéité amenant progressivement à 8 pour 29, si 29 il y a.

Cependant, comme c'est juste une intuition, je me garderais bien d'en faire une contrainte qui serait même plus forte que celle évoquée : au rang n n'accepter que les solutions ayant 8*n/29 (par exemple pour n=18, viser 5 et n'accepter que, globalement, 28*5 et 1*4) ce qui laisserait peu de choix, peut-être aucun.

C'est typiquement une idée qui ne pourrait être confirmée - ou pas - qu'avec une solution

Salutations

[tbc92]

En fait, je procède exactement comme tu suggérais dans ta précédente intervention. Je commence par placer des petits nombres. Quand j'ai choisi les 3 premières lignes, j'ai différents choix pour la 4ème ligne, mais seuls certains choix sont intéressants Inutile de tester des options qui sont différentes, mais 'topologiquement' identiques.
Si tu es motivé, il y a une démarche qui peut être utile :
- Partir de la solution avec 18 lignes présentée plus haut.
- Partant de cette solution, supprimer 5 ou 6 lignes aléatoirement (ou les lignes qui contiennent des 4 et des 5 mais pas de 8 par exemple ) et refaire une recherche exhaustive pour voir ce qu'on trouve.
- Et boucler plein de fois, en enlevant à chaque fois 5 ou 6 lignes nouvelles.
- Je pense qu'on ira pas au delà de 18 mais qui sait ?
- Et si on trouve d'autres solutions avec 18 lignes, faire le recensement de toutes ces solutions.
Ensuite, on peut se lancer dans une autre analyse : Si on constate que TOUTES les solutions ont un même profil, c'est une sacrée indication.
C'est quoi le profil dans ce contexte ? Ici, j'ai le 39 et le 18 qui apparaissent 4 fois, j'ai le 38 qui apparaît 5 fois .... et j'ai le 11 et le 12 qui apparaissent 6 fois, j'ai le 13 qui apparaît 8 fois. Le profil est donc 4.4.5.....6.6.8

[IME14]

J'ai fait quelques changements dans le programme, pour optimiser.
En quelques minutes, il trouve une solution pour 16 lignes ; puis au bout de plus d'une heure, il trouve une solution pour 17 lignes et juste après, 18 lignes, ... et depuis quelques heures... il cherche et cherche, mais pas mieux que 18 lignes.

Comment ton script détermine-t-il qu'il n'est pas possible de faire mieux que 18 lignes ? ?
On ne peut pas exclure qu'il n'y ai pas de solutions tant que ton programme n'a pas exploré tous les cas possibles. .

Si avec ces 'optimisations', le programme va vite, et arrive à la conclusion : au mieux, on arrive à 18 lignes, que peut-on en conclure ?
Rien.

Même avec ces modifications, ton programme aboutit toujours à 18 lignes ?

En examinant la solution à 18 lignes que tu as trouvée, on remarque qu'à la 3ᵉ ligne, il y a une incohérence : le couple (11:12) apparaît plus de deux fois (voir la 1ʳᵉ et la 2ᵉ ligne). Avec les observations que j'ai mentionnées,(- chaque paire de valeurs présentes dans une ligne apparaît exactement deux fois dans l’ensemble des lignes.) il semble que le programme ne puisse pas gérer correctement ces lignes. Par conséquent, il est possible qu’il puisse trouver une meilleure solution.

11:12:13:14:15:16:17:18:
11:12:19:20:21:22:23:24:
11:12:25:26:27:28:29:30:
11:13:19:25:31:32:33:34:
11:14:20:26:31:35:36:37:
11:15:21:27:32:35:38:39:
12:13:22:28:31:36:38:39:
12:16:20:29:33:34:35:38:
12:17:23:27:32:33:36:37:
13:14:21:23:28:30:33:35:
13:15:20:23:25:29:37:39:
13:16:21:22:26:27:34:37:
13:17:20:24:26:30:32:38:
13:18:19:24:27:29:35:36:
14:16:23:24:25:27:31:38:
14:17:19:20:27:28:34:39:
15:18:20:22:27:30:31:33:
16:18:20:21:25:28:32:36:

Cordialement,

[tbc92]

Ce n'est pas une erreur.
Je recopie ce que tu disais hier soir :

la demande est tjr la même :

Générer une matrice M de dimensions 29×8 où :
- Chaque ligne de la matrice représente un sous-ensemble de 8 entiers distincts, choisis parmi les entiers de 1 à 29.
- Chaque paire de lignes doit avoir exactement deux éléments en commun.

La contrainte 'une paire ne peut apparaître que 2 fois', c'est une contrainte que tu ajoutes, ou que tu enlèves, selon les jours.

Mon programme n'arrive pas toujours à 18 lignes. Très souvent, il arrive à des blocages après 14, 15 ou 16 lignes. Parfois, on arrive à 18 lignes. Je n'ai pas demandé au programme de générer un nouveau fichier à chaque fois qu'il arrive à 18 lignes, mais je sais que c'est arrivé plusieurs fois.
Mais aucun essai n'a permis de dépasser 18.