Résolution d'un graphe particulier [Résolu]

[Wachter]

Bonjour,

Je bloque sur le problème suivant illustré par l'image attachée à ce message.

Il faut placer des entiers naturels de 0 à 9 dans les cercles en respectant les règles ci-dessous :
1. Le nombre inscrit dans l'une des sept régions du graphe doit être égal au plus grand écart des entiers naturels inscrits dans deux cercles reliés par un arc dans cette même région.
2. Cet écart doit être atteint une et une seule fois.
3. Le chiffre inscrit dans le cercle en haut à gauche doit être au plus égal à 4.

Si vous avez un début de solution, je suis preneur !

Merci d'avance à vous.

[Trap D]

Ca se résoud facilement en Prolog avec une bibliothèque de contraintes.

[Wachter]

Il me faudrait une autoformation sur Prolog pour pouvoir m'en servir. En l'état actuel, je voudrais simplement résoudre ce problème même par tâtonnement. Je pense qu'il doit y avoir un algorithme qui résout ce problème.

Merci en tout cas de ton « début de solution ».

[galerien69]

hello,

tu mets une variable pour chaque noeud et apres algo du simplexe

[Wachter]

Salut,

Merci pour ta proposition qui me semble pertinente. Voici un début de formulation du programme linéaire :

Les variables du programmes : x0, x1, ..., x9 = {0, 1, ..., 9}
Les contraintes :
x0 <= 4 . . . . . (1)

Région 1 : (x1, x2) (x1, x6) (x2, x4) (x4, x6) grand écart = 5
max[(x1 - x2) (x1 - x6) (x2 - x4) (x4 - x6)] = 5 . . . . . (2)
(x1 - x2) ≠ (x1 - x6) ≠ (x2 - x4) ≠ (x4 - x6) . . . . . (3)

Région 2 : (x2, x3) (x2, x5) (x3, x5) grand écart = 3
Les mêmes contraintes que (2) et (3)

...

Région 7 : (x7, x8) (x7, x9) (x8, x10) (x9, x10) grand écart = 5
Les mêmes contraintes que (2) et (3)

Le problème qui se pose est comment transformer « max » et « ≠ » pour pouvoir lancer le programme. À moins qu'il existe un programme en ligne qui s'occupe de ces transformations !

Je ne sais pas si je suis sur la bonne voie. Il manque également la fonction objectif.

[Trap D]

max[(x1 - x2) (x1 - x6) (x2 - x4) (x4 - x6)] = 5 . . . . . (2)
(x1 - x2) ≠ (x1 - x6) ≠ (x2 - x4) ≠ (x4 - x6) . . . . . (3)

La règle (3) est fausse ! Tu peut fort bien avoir x1-x2 = x1-x6 s x1-x2 n'est pas la valeur maximale. (D'ailleur c'est le cas les solutions).

[galerien69]

J'ai ete un peu hatif dans la lecture de l'enonce.

Je ne suis pas sur que l'on puisse representer le OU dans les contraintes (max(x1-x2,x1-x6..)=5 -> x1-x2=5 OU x1-x6=5 ...)

mais peut etre est-ce le cas, je ne sais pas.

[Wachter]

Envoyé par Trap D

La règle (3) est fausse ! Tu peut fort bien avoir x1-x2 = x1-x6 s x1-x2 n'est pas la valeur maximale. (D'ailleur c'est le cas les solutions).

Effectivement. J'avais écrit à la va-vite la contrainte (3) en voulant traduire la règle « Cet écart doit être atteint une et une seule fois ».

[Wachter]

J'ai trouvé deux affectations. Trap D, pourrais-tu me dire s'il existe plus de deux solutions ?

[Trap D]

Je confirme (en allant de gauche à droite et de haut en bas :
[0,5,8,1,7,3,4,2,6,9] et [0,5,8,1,7,2,4,3,6,9]

Voici le code en SWI-Prolog

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
puzzle(L) :-
	% il y a dix nombres
	L = [A,B,C,D,E,F,G,H,I,J],
	% compris entre 0 et 9
	L ins 0..9,
	% tous différents
	all_distinct(L),

	% le premier est au maximum egal à 4
	A #< 5,
	
	% création des contraintes sur les arcs
	my_max([A, B, D, F, A], 5),
	my_max([B, C, E, B], 3),
	my_max([D, B, E, G, D], 4),
	my_max([F, D, H, I, F], 4),
	my_max([D, G, H, D], 3),
	my_max([G, E, C, J, G], 5),
	my_max([I, H, G, J, I], 5),
	
	% on calcule les possibilités
	label(L).



my_max(L, Max) :-
	calcule_max(Max, L, 0, 1).

make_max(Max, [A, B], R) :-
	% au maximum la difference est Max
	abs(A-B) #=< Max,
	% R vaut 1 si la différence est égale à Max
	% R vaut 0 sinon
	abs(A-B) #= Max #<==> R.


% règle de fin
% S'il n'y a plus qu'un point, 
% on unifie la valeur courante de R avec la valeur finale
calcule_max(_, [_], R, R).

% On parcours la liste des arcs
% on ajoute à chaque fois la valeur de R 
% qui indique l'égaliré à Max
% Le prédicat a été lancé avec 0
% A la fin on doit avoir 1 
% un seul arc doit avoir le maximum
calcule_max(Max, [A, B | T], R1, R) :-
	% on calcule la valeur de R pour cet arc
	make_max(Max, [A, B], R0),
	R2 #= R1 + R0,
	% on continue la boucle
	calcule_max(Max, [B | T], R2, R).