Re: Sugurus

Le 29/08/2021 à 08:49, robby a écrit :

si tu as une boite de taille N, alors ta contrainte "tous les nombres n_i de 1 à N sont présents" peut par exemple s'écrire sous la forme: v1*v2*v3*v4*v5 = 2*3*5*7*11 ( i.e. produit des N premiers nombres premiers ),   où la valeur n_i pour une  case est encodée comme v_i = n_i ème nombre premier

Oui et pareil pour les contraintes de proximités. Si j'appelle les variables Vij (1<=i,j<=N), on a aussi
Vij ~| V(i-1)(j+1) * V(i+0)j * V(i+1)j * Vi(j+1)    1<=i,j<N
(~| = "ne divise pas" a ~| b <=> b != 0 (mod a) ).
Cette relation "~|" permet d'encoder efficacement pas mal de contraintes et ainsi ramener n'importe quel Suguru de n cases à r régions avec i indices à une résolution de (n+r+i-1) équations en nombre entiers.
Exemple:
     C1 A  A        a  b  c
     C  B3 B   ->   d  e  f
     C  B  B        g  h  i
qui est de 9 cases avec 3 régions et 2 indices (les entier en colonne impaires sont les indices, les lettres en colonne paires sont les régions) s'encode avec les 9+3+2-1=13 contraintes suivantes:
trouver a,b,c,d,e,f,h,i,j entiers naturels tels que
## indices:
a | 2       ( a divise deux, e divise 3 )
e | 3     ( --> a = 2, e = 3          )
## régions:
bc   | 6    ( (b,c)=(2,3) ou (3,2) )
adg  | 30   ( -->  dg | 15         )
efgh | 210  ( --> fgh | 70         )
## proximité
a ~| bed    ( a ne divise pas b*e*d )
b ~| cfed   ( ce qui encore a != b, )
c ~| ef     ( et a != e, et a != d  )
d ~| ehg
e ~| fihg
f ~| ih
g ~| h
h ~| i
J'ai pas tenté de voir si les solveurs numérique savent manger ce genre d'équations, par contre cela permet peut-être d'appliquer des théorèmes d'arithmétique entière.
sam.