Discussion :

[baeri]

Bonsoir!

J'ai fait de mon mieux pour le titre, de toute façon on ne peut pas résumer un truc pareil

J'ai passé mon week-end sur un problème qui a vraiment fini par me prendre la tête. Je vais tenter d'expliquer le problème :
Nous avons un tableau à double entrée de 8*8 (toujours carré!), et chaque cellule de ce tableau dispose de 2 états disons 0 et 1. Le tableau est initialisé à 0.
Comme contrainte, nous avons l'obligation de placer quatre '1' dans chaque ligne, même chose dans chaque colonne. (Ni plus ni moins)
Le but est de générer tout les tableaux différents répondants à ces critères.

J'aimerais faire ça récursivement mais je n'arrive absolument pas à le faire, j'ai tenté des choses de ce genre :

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
generer(i, j, n) {
	if(n <= 8!/(4!*4!)*8) { 
 
		cells[i][j] = 1;
 
		if check(cells)
			print cells;
 
		if (i%8 == 0)
			i++; j = 0;
		else
			j++;
 
		calcul(i, j+1, n+1);
	}
}

évidemment sans succès.
(J'espère que ce pseudo-code est clair, 2-3 éclaircissements : check vérifie que le tableau actuel respect les contraintes et si oui on le garde (=on l'imprime). Et si mes souvenirs des cours de math sont bons, 8*8!/(4!*4!) est le nombre de tableaux possibles.)

Merci d'avance si vous pouvez me donner un coup de main, corriger mon pseudo-code, me lancer une idée..



Je précise que j'ai passé du temps et sur google et sur les cours de récursivité de developpez.com, sans succès. J'ai parfois de la peine à savoir quoi chercher, car même si c'est clair dans ma tête je ne connais pas les termes exacts pour formuler mes questions...

[Trap D]

Va faire un tour sur le forum prolog, regarde l'exemple de programmation par contrainte (exemple Sudoku) de pcaboche.

[millie]

Va faire un tour sur le forum prolog, regarde l'exemple de programmation par contrainte (exemple Sudoku) de pcaboche.

Je ne suis pas sûr qu'il souhaite un programme logique (et utilisant des contraintes), mais plutôt un algorithme impératif (voir fonctionnel)

[Zavonen]

A priori vous cherchez certaines parties à 32 éléments d'un ensemble à 64 éléments. Le nombre des possibilités est énorme
MAIS, désignons par a, b, c , d le nombre de points dans chaque 'quart' du carré.
Vous devez avoir a+b=c+d=a+c=b+d=16, ce qui limite déjà les possibilités.
De plus la possibilité 15,1,1,15 peut être immédiatement exclue, pour cause de découpage horizontal (le 1 serait isolé).
De même que 14-2 par coupage en 4. de fait chacun des nombres a,b,c,d doit être un multiple de 4.
Il reste donc
12,4,12,4
4,12,4,12
8,8,8,8
Par ailleurs les solutions de déduisent les unes des autres par les isométries du carré engendrées par 4 rotations et deux symétries axiales.
Vous pouvez donc vous concentrer sur les deux cas
12,4,12,4
8,8,8,8
Je ne suis pas sûr que le premier cas conduise à des solutions mais je ne peux l'exclure a priori.
Ce cas se traite assez vite vu le nombre restreint des possibilités
Pour les parties à 8 éléments d'un ensemble à 16, le nombre des possibles est 12870 (raisonnable)
On les classe alors par groupes selon la décomposition de 8 en somme de 8 nombres au plus égaux à 4.i
Il reste à les combiner 2 par deux pour remplir la partie supérieure du tableau en respectant la compatibilité des cas (on n'essaiera pas de combiner un 4+4 avec un 1+1+1+1+1+1+1+1 par exemple)
La partie inférieure, s'en déduit forcément par une transformation géométrique simple, sans garantie que le tableau obtenu soit une solution.
Bref, tout cela n'est pas très simple, mais je ne vois rien d'autre pour le moment

[baeri]

Bonjour et merci pour vos réponses!

Trap D & millie > En effet, je cherche à faire dans la programmation impérative plutôt que logique. (Et PROLOG est un outil merveilleux que je ne maitrise malheureusement pas.)

Zavonen > Merci pour votre longue réponse, d'abord. Ensuite, je dois bien avouer n'avoir pas compris votre vision des choses, à moins que vous n'ayez pas compris ce que je cherche à faire (ce qui ne serait pas étonnant vu que j'explique mal ).
Prenons le damier 8x8, le but est d'y placer 32 pions de façon à ce qu'il y ait 4 pions dans chaque colonne et chaque ligne.
Vous donnez certaines possibilités de subdivision du tableau en quarts avec le nombre de pions dans chaque quart, mais qu'est-ce qui empêche d'avoir la solution
16-0
0-16 ?
(
11110000
11110000
11110000
11110000
00001111
00001111
00001111
00001111
)
La contrainte étant respectée...?

Enfin, bien que votre approche du problème soit très séduisante, je serais plus intéressé par une aide expliquant comment, récursivement, générer toutes les permutations possibles d'un tableau (défini ci-dessus) en n'ayant qu'une possibilité de chaque cas de figure. (Toutes les permutations uniques.)
Ceci m'intéresse plus que l'implémentation directe du respect de la contrainte dans l'algo lui-même.

Merci d'avance à tous

[FrancisSourd]

Dans le pseudo-code que tu donnes au début, j'imagine que générer et calcul sont la même fonction appelée récursivement.

Le principal problème c'est que tu ne considères que le cas où la cellule est mise à 1 alors qu'il faut considérer le 2 cas 1 ou 0, ce qui se traduit par 2 appels récursifs. Pour bien comprendre cela, tout ce qui touche aux arbres d'énumérations te sera fort utile!

Je n'ai pas vérifié ton expression du nombre de solutions(comment l'as-tu obtenu?) mais, une chose est sûre, c'est qu'elle n'est pas très utile pour la génération.

[baeri]

Merci pour ta réponse, je vais me renseigner sur ces arbres d'énumérations.
Quant aux 2 appels récursifs, je ne vois vraiment pas comment les placer. Et oui, la fonction calcul sert à générer les tableaux récursivement.

En ce qui concerne le nombre de tableaux possibles, j'ai compté sans contrainte. En math le dénombrement des permutations possibles de k éléments dont les éléments sont distincts est simple, on fait k!
Si parmi nos éléments nous avons un groupe de x éléments identiques, un groupe de y éléments identiques mais différent de x et ainsi de suite pour z, le nombre de permutation de l'ensemble k est k!/(x!y!z!)

Là, une ligne de mon tableau est composée de 8 éléments dont 4 sont des '1' et 4 des '0'. Le nombre de lignes différentes qu'il est possible d'obtenir est donc 8!/(4!*4!)
Et j'ai naïvement multiplié le tout par 8, car mon tableau est composé de 8 lignes.


Malgré toutes vos informations je n'arrive toujours pas à générer récursivement tout les tableaux de 8x8 possédant 16 cases remplies et les autres vides.

[Zavonen]

Bonjour et merci pour vos réponses!

Zavonen > Merci pour votre longue réponse, d'abord. Ensuite, je dois bien avouer n'avoir pas compris votre vision des choses, à moins que vous n'ayez pas compris ce que je cherche à faire (ce qui ne serait pas étonnant vu que j'explique mal ).
Prenons le damier 8x8, le but est d'y placer 32 pions de façon à ce qu'il y ait 4 pions dans chaque colonne et chaque ligne.
Vous donnez certaines possibilités de subdivision du tableau en quarts avec le nombre de pions dans chaque quart, mais qu'est-ce qui empêche d'avoir la solution
16-0
0-16 ?
(
11110000
11110000
11110000
11110000
00001111
00001111
00001111
00001111
)
La contrainte étant respectée...?

J'ai bien compris le pb que vous avez exliqué clairement
Et bien, vous avez raison, j'ai OUBLIE cette possibilité que rien n'exclut dans mes équations.
16-0-16-0 et évidemment
0-16-0-16
Mais mon raisonnement sur les quarts, je crois tient toujours.
Donc, à permutation près par symétries. Il me SEMBLE que les seules répartitions possibles sont:
0-16-0-16
4-12-4-12
8-8-8-8
Pour le premier cas la solution que vous proposez est la seule.
Pour le second cas, pour faire un demi-tableau, il y a 420 façons de poser 4 pions sur un carré 4*4 et autant pour 12 pions mais il est clair que le total à considérer n'est pas 420*420 car il y a incompatibilité dès que 5 pions ou plus sont une même ligne. on peut je pense trouver toutes les possibilités, même par une étude exhaustive.
Le dernier cas est le plus difficile à traiter.