%% ========================================================
%% Auteur: Jean-Michel Richer
%% email: jean-michel.richer@univ-angers.fr
%% ========================================================
%%
%% Problème de coloriage de RAMSEY :
%%
%%    Etant donné un graphe complet de N sommets, trouver
%%    un coloriage en 3 couleurs (Rouge, Vert, Bleu) de 
%%    manière à ce qu'il n'existe pas de triangle mono-
%%    chromatique.
%%    Ce problème possède des solutions pour N = 3 à 16.
%%
%% ========================================================

include "globals.mzn";

%% --------------------------
%%         Variables
%% --------------------------

int: N = 10;

array[1..N,1..N] of var 0..1 : R;
array[1..N,1..N] of var 0..1 : G;
array[1..N,1..N] of var 0..1 : B;

%% --------------------------
%%        Constraints
%% --------------------------

constraint forall(i in 1..N-1) (
  forall(j in i+1..N) (
      R[i,j] + G[i,j] + B[i,j] = 1
    )
);

constraint forall(i in 1..N-2) (
  forall(j in i+1..N-1) (
    forall(k in j+1..N) (
      R[i,j] + R[i,k] + R[j,k] <= 2
    )
  )
);

constraint forall(i in 1..N-2) (
  forall(j in i+1..N-1) (
    forall(k in j+1..N) (
      G[i,j] + G[i,k] + G[j,k] <= 2
    )
  )
);

constraint forall(i in 1..N-2) (
  forall(j in i+1..N-1) (
    forall(k in j+1..N) (
      B[i,j] + B[i,k] + B[j,k] <= 2
    )
  )
);

%% --------------------------
%%          Search
%% --------------------------

solve satisfy;