1. Coder les couleurs 

>	P:=proc(x,m) local i; mul(x-i,i=1..m) end;

 

2. Couleurs différentes 

>	Q:=proc(x,y,m) if x=y then NULL else normal((P(x,m)-P(y,m))/(x-y)) fi end;

 

3. Les arêtes du graphe 

>	with(GraphTheory):

 

>	pays := [argentine, paraguay, venezuela, colombie, guyane, bresil, surinam, chili, uruguay, bolivie, perou, guyana, equateur];

 

>	AmeriqueDuSud:=Graph(pays,Trail(guyane,surinam,guyana,venezuela,colombie,equateur,perou,bolivie,chili,argentine,uruguay));

 

>	for v in [guyane, surinam,guyana, venezuela, colombie, perou, bolivie, paraguay, argentine, uruguay] do AddEdge(AmeriqueDuSud,{bresil,v}) od:

 

>	AddEdge(AmeriqueDuSud,{{colombie,perou},{perou,chili},{argentine,bolivie},{argentine,paraguay},{paraguay,bolivie}});

 

>	DrawGraph(AmeriqueDuSud);

 

4. Coloriage de la carte 

>	sys:=proc(G,m) local v, e;{seq(P(v,m),v=Vertices(G))} union {seq(Q(op(e),m),e=Edges(G))} end;

 

>	Groebner[Basis](sys(AmeriqueDuSud,3),tdeg(op(pays)));

 

>	G:=Groebner[Basis](sys(AmeriqueDuSud,4),tdeg(op(pays))):

 

G est différent de [1], donc le système a des solutions. On peut les compter : 

>	PolynomialIdeals[NumberOfSolutions](PolynomialIdeals[PolynomialIdeal](sys(AmeriqueDuSud,4),known_grobner_basis=[tdeg(op(pays))=G]));

 

Il y a donc beaucoup de solutions. 

Pour commencer, on peut fixer la couleur du Brésil à 1 : 

>	G2:=Groebner[Basis]({op(G)} union {bresil-1},tdeg(op(pays)));

 

>	map(factor,%);

 

On voit qu'il reste 4 choix pour l'Équateur. On peut fixer par exemple la couleur de l'Équateur à la même que celle du Brésil : 

>	G3:=map(factor,Groebner[Basis]({op(G2)} union {equateur-1},tdeg(op(pays))));

 

Le Chili a encore 4 choix. À nouveau, on peut décider par exemple que le Chili a la même couleur que le Brésil : 

>	G4:=map(factor,Groebner[Basis]({op(G3)} union {chili-1},tdeg(op(pays))));

 

On décide maintnenat que le Venezuela, la Bolivie, l'Uruguay et le Surinam ont par exemple la couleur 2, 

>	G5:=map(factor,Groebner[Basis]({op(G4)} union {venezuela-2,bolivie-2,uruguay-2,surinam-2},tdeg(op(pays))));

 

Il reste peu de solutions. On peut encore fixer les couleurs de Guyane, Guyana, Pérou et Paraguay à 3 : 

>	Groebner[Basis]({op(G5)} union {guyane-3,guyana-3,perou-3,paraguay-3},tdeg(op(pays)));

 

5. Le Sudoku 

D'abord les polynômes qui ne dépendent pas de la grille : 

>	sn:=3:n:=sn^2:

 

>	rows:={seq({seq(x[i,j],j=1..n)},i=1..n)}:

 

>	cols:={seq({seq(x[i,j],i=1..n)},j=1..n)}:

 

>	blocks:={seq(seq({seq(seq(x[i*sn+ii,j*sn+jj],ii=1..sn),jj=1..sn)},i=0..sn-1),j=0..sn-1)}:

 

>	sys1:={seq(seq(P(x[i,j],9),i=1..n),j=1..n)}:

 

>	sys2:={seq(seq(seq(Q(pt1,pt2,9),pt1=rel),pt2=rel),rel= rows union cols union blocks)}:

 

Ensuite, la grille elle-même : 

>	sys3:={x[1,1]-5,x[2,2]-9,x[3,1]-4,x[3,3]-7,x[1,5]-8,x[2,6]-5,x[3,4]-1,x[1,8]-4,x[2,7]-7,x[2,8]-1,x[6,1]-9,x[6,3]-8,x[4,5]-3,x[5,5]-6,x[4,9]-4,x[5,8]-7,x[6,7]-3,x[6,9]-6,x[7,3]-9,x[8,2]-4,x[9,3]-3,x[7,6]-8,x[8,5]-7,x[9,4]-4,x[9,5]-1,x[9,6]-6,x[8,7]-5,x[9,7]-9,x[9,8]-8}:

 

Finalement, la résolution : 

>	Groebner[Basis](sys1 union sys2 union sys3, tdeg(seq(seq(x[i,j],j=1..n),i=1..n)));

 

On peut visualiser la grille résolue : 

>	subs(solve(%,indets(%)),Matrix([seq([seq(x[i,j],j=1..n)],i=1..n)]));

 

6. En enlevant une contrainte 

>	sys4:=remove(has,sys3,x[1,1]);

 

>	Groebner[Basis](sys1 union sys2 union sys4, tdeg(seq(seq(x[i,j],j=1..n),i=1..n)));

 

>	PolynomialIdeals[NumberOfSolutions](PolynomialIdeals[PolynomialIdeal](%),tdeg(seq(seq(x[i,j],i=1..n),j=1..n)));